The Power of Constraint Grammars Revisited

Anssi Mikael Yli-Jyrä

The Power of Constraint Grammars Revisited

Language Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

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.

Translated title of the contribution	Rajoitekieliopin ilmaisuvoiman uudelleentarkastelua
Original language	English
Title of host publication	Proceedings of the NoDaLiDa 2017 Workshop on Constraint Grammar - Methods, Tools and Applications : Linköping Electronic Conference Proceedings 140
Editors	Eckhard Bick, Trond Trosterud
Number of pages	9
Volume	140
Place of Publication	Linköping
Publisher	Linköping University Electronic Press
Publication date	2017
Pages	23-31
ISBN (Print)	978-91-7685-465-5
ISBN (Electronic)	978-91-7685-465-5
Publication status	Published - 2017
MoE publication type	A4 Article in conference proceedings
Event	NoDaLiDa 2017 Workshop on Constraint Grammar - Methods, Tools and Applications - Göteborg, Sweden Duration: 22 May 2017 → 22 May 2017 Conference number: 21

Publication series

Name	NEALT Proceedings Series
Publisher	Linköping University Electronic Press, Linköpings universitet
Volume	33
ISSN (Print)	1650-3686
ISSN (Electronic)	1650-3740

Fields of Science

6121 Languages

Access to Document

ThePowerofConstraintGrammarRevisitedFinal published version, 294 KB

Cite this

@inproceedings{26724d35da6e49fa95dd1dc796178bd6,

title = "The Power of Constraint Grammars Revisited",

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.",

keywords = "6121 Languages",

author = "Yli-Jyr{\"a}, {Anssi Mikael}",

note = " Proceeding volume: 140; NoDaLiDa 2017 Workshop on Constraint Grammar - Methods, Tools and Applications ; Conference date: 22-05-2017 Through 22-05-2017",

year = "2017",

language = "English",

isbn = "978-91-7685-465-5",

volume = "140",

series = "NEALT Proceedings Series",

publisher = "Link{\"o}ping University Electronic Press",

pages = "23--31",

editor = "Eckhard Bick and Trond Trosterud",

booktitle = "Proceedings of the NoDaLiDa 2017 Workshop on Constraint Grammar - Methods, Tools and Applications",

address = "Sweden",

}

Yli-Jyrä, AM 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.

The Power of Constraint Grammars Revisited. / Yli-Jyrä, Anssi Mikael.
Proceedings of the NoDaLiDa 2017 Workshop on Constraint Grammar - Methods, Tools and Applications: Linköping Electronic Conference Proceedings 140. ed. / Eckhard Bick; Trond Trosterud. Vol. 140 Linköping: Linköping University Electronic Press, 2017. p. 23-31 (NEALT Proceedings Series; Vol. 33).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

TY - GEN

T1 - The Power of Constraint Grammars Revisited

AU - Yli-Jyrä, Anssi Mikael

N1 - Conference code: 21

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

KW - 6121 Languages

M3 - Conference contribution

SN - 978-91-7685-465-5

VL - 140

T3 - NEALT Proceedings Series

SP - 23

EP - 31

BT - Proceedings of the NoDaLiDa 2017 Workshop on Constraint Grammar - Methods, Tools and Applications

A2 - Bick, Eckhard

A2 - Trosterud, Trond

PB - Linköping University Electronic Press

CY - Linköping

T2 - NoDaLiDa 2017 Workshop on Constraint Grammar - Methods, Tools and Applications

Y2 - 22 May 2017 through 22 May 2017

ER -

The Power of Constraint Grammars Revisited

Abstract

Publication series

Fields of Science

Access to Document

Other files and links

ADEQSYNTAX: A Usable Finite-State Model for Adequate Syntactic Complexity

Cite this

The Power of Constraint Grammars Revisited

Abstract

Publication series

Fields of Science

Access to Document

Other files and links

Projects

ADEQSYNTAX: A Usable Finite-State Model for Adequate Syntactic Complexity

Cite this