Consensual languages and matching finite-state computations
Stefano Crespi Reghizzi; Pierluigi San Pietro
RAIRO - Theoretical Informatics and Applications (2011)
- Volume: 45, Issue: 1, page 77-97
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topCrespi Reghizzi, Stefano, and San Pietro, Pierluigi. "Consensual languages and matching finite-state computations." RAIRO - Theoretical Informatics and Applications 45.1 (2011): 77-97. <http://eudml.org/doc/222057>.
@article{CrespiReghizzi2011,
abstract = {
An ever present, common sense idea in language modelling research is that, for a
word to be a valid phrase, it should comply with multiple constraints at
once. A new language definition model is studied, based on agreement or consensus
between similar strings. Considering a regular set of strings over a bipartite
alphabet made by pairs of unmarked/marked symbols, a match relation is
introduced, in order to specify when such strings agree. Then a regular set
over the bipartite alphabet can be interpreted as specifying another language
over the unmarked alphabet, called the consensual language. A word is in the
consensual language if a set of corresponding matching strings is in the
original language. The family thus defined includes the regular languages and
also interesting non-semilinear ones. The word problem can be solved in
NLOGSPACE, hence in P time.
The emptiness problem is undecidable.
Closure properties are
proved for intersection with regular sets and inverse alphabetical homomorphism.
Several conditions for a consensual definition to yield a regular language are
presented, and it is shown that the size of a consensual specification of
regular languages can be in a logarithmic ratio with respect to a DFA. The
family is incomparable with context-free and tree-adjoining grammar families.
},
author = {Crespi Reghizzi, Stefano, San Pietro, Pierluigi},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Formal languages; finite automata; consensual languages; counter machines; polynomial time
parsing; non-semilinear languages; Parikh mapping; descriptive complexity of regular languages; degree of grammaticality; formal languages; polynomial time parsing},
language = {eng},
month = {3},
number = {1},
pages = {77-97},
publisher = {EDP Sciences},
title = {Consensual languages and matching finite-state computations},
url = {http://eudml.org/doc/222057},
volume = {45},
year = {2011},
}
TY - JOUR
AU - Crespi Reghizzi, Stefano
AU - San Pietro, Pierluigi
TI - Consensual languages and matching finite-state computations
JO - RAIRO - Theoretical Informatics and Applications
DA - 2011/3//
PB - EDP Sciences
VL - 45
IS - 1
SP - 77
EP - 97
AB -
An ever present, common sense idea in language modelling research is that, for a
word to be a valid phrase, it should comply with multiple constraints at
once. A new language definition model is studied, based on agreement or consensus
between similar strings. Considering a regular set of strings over a bipartite
alphabet made by pairs of unmarked/marked symbols, a match relation is
introduced, in order to specify when such strings agree. Then a regular set
over the bipartite alphabet can be interpreted as specifying another language
over the unmarked alphabet, called the consensual language. A word is in the
consensual language if a set of corresponding matching strings is in the
original language. The family thus defined includes the regular languages and
also interesting non-semilinear ones. The word problem can be solved in
NLOGSPACE, hence in P time.
The emptiness problem is undecidable.
Closure properties are
proved for intersection with regular sets and inverse alphabetical homomorphism.
Several conditions for a consensual definition to yield a regular language are
presented, and it is shown that the size of a consensual specification of
regular languages can be in a logarithmic ratio with respect to a DFA. The
family is incomparable with context-free and tree-adjoining grammar families.
LA - eng
KW - Formal languages; finite automata; consensual languages; counter machines; polynomial time
parsing; non-semilinear languages; Parikh mapping; descriptive complexity of regular languages; degree of grammaticality; formal languages; polynomial time parsing
UR - http://eudml.org/doc/222057
ER -
References
top- A.K. Chandra, D. Kozen and L.J. Stockmeyer, Alternation. J. ACM28 (1981) 114–133.
- S. Crespi Reghizzi and P. San Pietro, Consensual definition of languages by regular sets, in LATA. Lecture Notes in Computer Science5196 (2008) 196–208.
- S. Crespi Reghizzi and P. San Pietro, Languages defined by consensual computations. in ICTCS09 (2009).
- M. Jantzen, On the hierarchy of Petri net languages. ITA13 (1979).
- A. Joshi and Y. Schabes, Tree-adjoining grammars, in Handbook of Formal Languages, Vol. 3, G. Rozenberg and A. Salomaa, Eds. Springer, Berlin, New York (1997), 69–124.
- M. Minsky, Computation: Finite and Infinite Machines. Prentice-Hall, Englewood Cliffs (1976).
- A. Salomaa, Theory of Automata. Pergamon Press, Oxford (1969).
- K. Vijay-Shanker and D.J. Weir, The equivalence of four extensions of context-free grammars. Math. Syst. Theor.27 (1994) 511–546.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.