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 : 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},
     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] A.K. Chandra, D. Kozen and L.J. Stockmeyer, Alternation. J. ACM 28 (1981) 114-133. | MR | Zbl

[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 | Zbl

[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 | Zbl

[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

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

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

[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 | Zbl

Cité par Sources :