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.

Classification: 68Q45, 68Q42, 68Q19

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

@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}, publisher = {EDP-Sciences}, volume = {45}, number = {1}, year = {2011}, pages = {77-97}, doi = {10.1051/ita/2011012}, zbl = {1219.68112}, mrnumber = {2776855}, language = {en}, url = {http://www.numdam.org/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, Volume 45 (2011) no. 1, pp. 77-97. doi : 10.1051/ita/2011012. http://www.numdam.org/item/ITA_2011__45_1_77_0/

[1] Alternation. J. ACM 28 (1981) 114-133. | MR 603186 | Zbl 0473.68043

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

and ,[3] Languages defined by consensual computations. in ICTCS09 (2009).

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

,[5] 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

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

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

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

and ,