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
Alternative title: Rajoitekieliopin ilmaisuvoiman uudelleentarkastelua
Author: Yli-Jyrä, Anssi Mikael
Other contributor: Bick, Eckhard
Trosterud, Trond
Contributor organization: Department of Modern Languages 2010-2017
Anssi Mikael Yli-Jyrä / Principal Investigator
Language Technology
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
Belongs to series: NEALT Proceedings Series
ISBN: 978-91-7685-465-5
978-91-7685-465-5
ISSN: 1650-3686
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.
Description: Proceeding volume: 140
Subject: 6121 Languages
Peer reviewed: Yes
Usage restriction: openAccess
Self-archived version: publishedVersion
Funder: Suomen tietokirjailijat
Grant number:


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