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.

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.

DOI : https://doi.org/10.1051/ita/2011012
Classification : 68Q45,  68Q42,  68Q19
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},
zbl = {1219.68112},
mrnumber = {2776855},
language = {en},
url = {http://www.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
DA  - 2011///
SP  - 77
EP  - 97
VL  - 45
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2011012/
UR  - https://zbmath.org/?q=an%3A1219.68112
UR  - https://www.ams.org/mathscinet-getitem?mr=2776855
UR  - https://doi.org/10.1051/ita/2011012
DO  - 10.1051/ita/2011012
LA  - en
ID  - ITA_2011__45_1_77_0
ER  - 
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://www.numdam.org/articles/10.1051/ita/2011012/

[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

Cité par Sources :