The Power of Constraint Grammars Revisited

Anssi Mikael Yli-Jyrä

The Power of Constraint Grammars Revisited

Språkteknologi

Forskningsoutput: Kapitel i bok/rapport/konferenshandling › Konferensbidrag › Vetenskaplig › Peer review

Sammanfattning

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 titel	Rajoitekieliopin ilmaisuvoiman uudelleentarkastelua
Originalspråk	engelska
Titel på värdpublikation	Proceedings of the NoDaLiDa 2017 Workshop on Constraint Grammar - Methods, Tools and Applications : Linköping Electronic Conference Proceedings 140
Redaktörer	Eckhard Bick, Trond Trosterud
Antal sidor	9
Volym	140
Utgivningsort	Linköping
Förlag	Linköping University Electronic Press
Utgivningsdatum	2017
Sidor	23-31
ISBN (tryckt)	978-91-7685-465-5
ISBN (elektroniskt)	978-91-7685-465-5
Status	Publicerad - 2017
MoE-publikationstyp	A4 Artikel i en konferenspublikation
Evenemang	NoDaLiDa 2017 Workshop on Constraint Grammar - Methods, Tools and Applications - Göteborg, Sverige Varaktighet: 22 maj 2017 → 22 maj 2017 Konferensnummer: 21

Publikationsserier

Namn	NEALT Proceedings Series
Förlag	Linköping University Electronic Press, Linköpings universitet
Volym	33
ISSN (tryckt)	1650-3686
ISSN (elektroniskt)	1650-3740

Vetenskapsgrenar

6121 Språkvetenskaper

Åtkomst av dokument

ThePowerofConstraintGrammarRevisitedSlutlig publicerad version, 294 KB

Andra filer och länkar

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

1 Slutfört

ADEQSYNTAX: Käytettävä äärellistilainen malli adekvaatille kieliopilliselle kompleksisuudelle
Yli-Jyrä, A.
Suomen tietokirjailijat
01/09/2013 → 30/04/2019
Projekt: Forskningsprojekt

Citera det här

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

Forskningsoutput: Kapitel i bok/rapport/konferenshandling › Konferensbidrag › Vetenskaplig › 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

Sammanfattning

Publikationsserier

Vetenskapsgrenar

Åtkomst av dokument

Andra filer och länkar

Projekt

ADEQSYNTAX: Käytettävä äärellistilainen malli adekvaatille kieliopilliselle kompleksisuudelle

Citera det här