The Power of Constraint Grammars Revisited

Aktiviteetti: Puhe- tai esitystyypitSuullinen esitys


Sequential Constraint Grammar (SCG)
(Karlsson, 1990) and its extensions have
lacked clear connections to formal language
theory. The purpose of this article is
to lay a foundation for these connections
by simplifying the definition of strings
processed by the grammar and by showing
that Nonmonotonic SCG is undecidable
and that derivations similar to the Generative
Phonology exist. The current investigations
propose resource bounds that
restrict the generative power of SCG to
a subset of context sensitive languages
and present a strong finite-state condition
for grammars as wholes
Aikajakso11 toukok. 2017