Consensual languages and matching finite-state computations
Crespi Reghizzi, Stefano ; San Pietro, Pierluigi
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011), p. 77-97 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2011-01-01
DOI : https://doi.org/10.1051/ita/2011012
Classification:  68Q45,  68Q42,  68Q19 
@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},
     volume = {45},
     year = {2011},
     pages = {77-97},
     doi = {10.1051/ita/2011012},
     mrnumber = {2776855},
     zbl = {1219.68112},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 77-97. doi : 10.1051/ita/2011012. http://gdmltest.u-ga.fr/item/ITA_2011__45_1_77_0/

[1] A.K. Chandra, D. Kozen and L.J. Stockmeyer, Alternation. J. ACM 28 (1981) 114-133. | MR 603186 | Zbl 0473.68043

[2] S. Crespi Reghizzi and P. San Pietro, Consensual definition of languages by regular sets, in LATA. Lecture Notes in Computer Science 5196 (2008) 196-208. | MR 2540324 | Zbl 1156.68452

[3] S. Crespi Reghizzi and P. San Pietro, Languages defined by consensual computations. in ICTCS09 (2009).

[4] M. Jantzen, On the hierarchy of Petri net languages. ITA 13 (1979). | Numdam | MR 525455 | Zbl 0404.68076

[5] 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. | MR 1470019

[6] M. Minsky, Computation: Finite and Infinite Machines. Prentice-Hall, Englewood Cliffs (1976). | MR 356580 | Zbl 0195.02402

[7] A. Salomaa, Theory of Automata. Pergamon Press, Oxford (1969). | MR 262021 | Zbl 0193.32901

[8] K. Vijay-Shanker and D.J. Weir, The equivalence of four extensions of context-free grammars. Math. Syst. Theor. 27 (1994) 511-546. | MR 1288685 | Zbl 0813.68129