The Power of Constraint Grammars Revisited

Forskningsoutput: Kapitel i bok/rapport/konferenshandlingKonferensbidragVetenskapligPeer review


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. We show that a grammar is equivalent to a finite-state transducer if it is implemented with a Turing machine that runs in o(n log n) time. This condition opens new finite-state hypotheses and avenues for deeper analysis of SCG instances in the way inspired by Finite-State Phonology.
Bidragets översatta titelRajoitekieliopin ilmaisuvoiman uudelleentarkastelua
Titel på värdpublikationProceedings of the NoDaLiDa 2017 Workshop on Constraint Grammar - Methods, Tools and Applications : Linköping Electronic Conference Proceedings 140
RedaktörerEckhard Bick, Trond Trosterud
Antal sidor9
FörlagLinköping University Electronic Press
ISBN (tryckt)978-91-7685-465-5
ISBN (elektroniskt)978-91-7685-465-5
StatusPublicerad - 2017
MoE-publikationstypA4 Artikel i en konferenspublikation
EvenemangNoDaLiDa 2017 Workshop on Constraint Grammar - Methods, Tools and Applications - Göteborg, Sverige
Varaktighet: 22 maj 201722 maj 2017
Konferensnummer: 21


NamnNEALT Proceedings Series
FörlagLinköping University Electronic Press, Linköpings universitet
ISSN (tryckt)1650-3686
ISSN (elektroniskt)1650-3740


  • 6121 Språkvetenskaper

Citera det här