The Power of Constraint Grammars Revisited

Anssi Mikael Yli-Jyrä

The Power of Constraint Grammars Revisited

Julkaisun otsikon käännös: Rajoitekieliopin ilmaisuvoiman uudelleentarkastelua

Kieliteknologia

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussa › Konferenssiartikkeli › Tieteellinen › vertaisarvioitu

Abstrakti

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.

Julkaisun otsikon käännös	Rajoitekieliopin ilmaisuvoiman uudelleentarkastelua
Alkuperäiskieli	englanti
Otsikko	Proceedings of the NoDaLiDa 2017 Workshop on Constraint Grammar - Methods, Tools and Applications : Linköping Electronic Conference Proceedings 140
Toimittajat	Eckhard Bick, Trond Trosterud
Sivumäärä	9
Vuosikerta	140
Julkaisupaikka	Linköping
Kustantaja	Linköping University Electronic Press
Julkaisupäivä	2017
Sivut	23-31
ISBN (painettu)	978-91-7685-465-5
ISBN (elektroninen)	978-91-7685-465-5
Tila	Julkaistu - 2017
OKM-julkaisutyyppi	A4 Artikkeli konferenssijulkaisuussa
Tapahtuma	NoDaLiDa 2017 Workshop on Constraint Grammar - Methods, Tools and Applications - Göteborg, Ruotsi Kesto: 22 toukok. 2017 → 22 toukok. 2017 Konferenssinumero: 21

Julkaisusarja

Nimi	NEALT Proceedings Series
Kustantaja	Linköping University Electronic Press, Linköpings universitet
Vuosikerta	33
ISSN (painettu)	1650-3686
ISSN (elektroninen)	1650-3740

Lisätietoja

Proceeding volume: 140

Tieteenalat

6121 Kielitieteet

Pääsy asiakirjaan

ThePowerofConstraintGrammarRevisitedLopullinen julkaistu versio, 294 KB

Muut tiedostot ja linkit

arXiv:1707.05115v1 [cs.FL] 17 Jul 201

1 Päättynyt

ADEQSYNTAX: A Usable Finite-State Model for Adequate Syntactic Complexity
Yli-Jyrä, A.
Suomen tietokirjailijat
01/09/2013 → 30/04/2019
Projekti: Tutkimusprojekti

Siteeraa tätä

Yli-Jyrä, A. M. (2017). The Power of Constraint Grammars Revisited. teoksessa E. Bick, & T. Trosterud (Toimittajat), Proceedings of the NoDaLiDa 2017 Workshop on Constraint Grammar - Methods, Tools and Applications: Linköping Electronic Conference Proceedings 140 (Vuosikerta 140, Sivut 23-31). (NEALT Proceedings Series; Vuosikerta 33). Linköping University Electronic Press.

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

@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. julkaisussa E Bick & T Trosterud (toim), Proceedings of the NoDaLiDa 2017 Workshop on Constraint Grammar - Methods, Tools and Applications: Linköping Electronic Conference Proceedings 140. Vuosikerta 140, NEALT Proceedings Series, Vuosikerta 33, Linköping University Electronic Press, Linköping, Sivut 23-31, NoDaLiDa 2017 Workshop on Constraint Grammar - Methods, Tools and Applications , Göteborg, Ruotsi, 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. toim. / Eckhard Bick; Trond Trosterud. Vuosikerta 140 Linköping : Linköping University Electronic Press, 2017. s. 23-31 (NEALT Proceedings Series; Vuosikerta 33).

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussa › Konferenssiartikkeli › Tieteellinen › vertaisarvioitu

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

Abstrakti

Julkaisusarja

Lisätietoja

Tieteenalat

Pääsy asiakirjaan

Muut tiedostot ja linkit

Projektit

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

Siteeraa tätä