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.
Mots-clés : formal languages, finite automata, consensual languages, counter machines, polynomial time parsing, non-semilinear languages, Parikh mapping, descriptive complexity of regular languages, degree of grammaticality
@article{ITA_2011__45_1_77_0,
author = {Crespi Reghizzi, Stefano and San Pietro, Pierluigi},
title = {Consensual languages and matching finite-state computations},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {77--97},
publisher = {EDP-Sciences},
volume = {45},
number = {1},
year = {2011},
doi = {10.1051/ita/2011012},
mrnumber = {2776855},
zbl = {1219.68112},
language = {en},
url = {http://archive.numdam.org/articles/10.1051/ita/2011012/}
}
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 SP - 77 EP - 97 VL - 45 IS - 1 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita/2011012/ DO - 10.1051/ita/2011012 LA - en ID - ITA_2011__45_1_77_0 ER -
%0 Journal Article %A Crespi Reghizzi, Stefano %A San Pietro, Pierluigi %T Consensual languages and matching finite-state computations %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2011 %P 77-97 %V 45 %N 1 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita/2011012/ %R 10.1051/ita/2011012 %G en %F ITA_2011__45_1_77_0
Crespi Reghizzi, Stefano; San Pietro, Pierluigi. Consensual languages and matching finite-state computations. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011) no. 1, pp. 77-97. doi : 10.1051/ita/2011012. http://archive.numdam.org/articles/10.1051/ita/2011012/
[1] , and , Alternation. J. ACM 28 (1981) 114-133. | MR | Zbl
[2] and , Consensual definition of languages by regular sets, in LATA. Lecture Notes in Computer Science 5196 (2008) 196-208. | MR | Zbl
[3] and , Languages defined by consensual computations. in ICTCS09 (2009).
[4] , On the hierarchy of Petri net languages. ITA 13 (1979). | Numdam | MR | Zbl
[5] and , Tree-adjoining grammars, in Handbook of Formal Languages, Vol. 3, G. Rozenberg and A. Salomaa, Eds. Springer, Berlin, New York (1997), 69-124. | MR
[6] , Computation: Finite and Infinite Machines. Prentice-Hall, Englewood Cliffs (1976). | MR | Zbl
[7] , Theory of Automata. Pergamon Press, Oxford (1969). | MR | Zbl
[8] and , The equivalence of four extensions of context-free grammars. Math. Syst. Theor. 27 (1994) 511-546. | MR | Zbl
Cité par Sources :
