Consensual languages and matching finite-state computations

Crespi Reghizzi, Stefano, and San Pietro, Pierluigi. "Consensual languages and matching finite-state computations." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 45.1 (2011): 77-97. <http://eudml.org/doc/272992>.

@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 - Informatique Théorique et 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},
language = {eng},
number = {1},
pages = {77-97},
publisher = {EDP-Sciences},
title = {Consensual languages and matching finite-state computations},
url = {http://eudml.org/doc/272992},
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 - Informatique Théorique et Applications
PY - 2011
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
UR - http://eudml.org/doc/272992
ER -