The Power of Constraint Grammars Revisited

Show full item record



Permalink

http://hdl.handle.net/10138/203762

Citation

Yli-Jyrä , A M 2017 , The Power of Constraint Grammars Revisited . in E Bick & T Trosterud (eds) , Proceedings of the NoDaLiDa 2017 Workshop on Constraint Grammar - Methods, Tools and Applications : Linköping Electronic Conference Proceedings 140 . vol. 140 , NEALT Proceedings Series , vol. 33 , Linköping University Electronic Press , Linköping , pp. 23-31 , NoDaLiDa 2017 Workshop on Constraint Grammar - Methods, Tools and Applications , Göteborg , Sweden , 22/05/2017 .

Title: The Power of Constraint Grammars Revisited
Author: Yli-Jyrä, Anssi Mikael
Editor: Bick, Eckhard; Trosterud, Trond
Contributor: University of Helsinki, Department of Modern Languages 2010-2017
Publisher: Linköping University Electronic Press
Date: 2017
Language: eng
Number of pages: 9
Belongs to series: Proceedings of the NoDaLiDa 2017 Workshop on Constraint Grammar - Methods, Tools and Applications Linköping Electronic Conference Proceedings 140
Belongs to series: NEALT Proceedings Series
ISBN: 978-91-7685-465-5
978-91-7685-465-5
URI: http://hdl.handle.net/10138/203762
Abstract: 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.
Subject: 6121 Languages
Rights:


Files in this item

Total number of downloads: Loading...

Files Size Format View
ThePowerofConstraintGrammarRevisited.pdf 294.1Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record