Consensual languages and matching finite-state computations.

*(English)*Zbl 1219.68112Summary: 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.

##### MSC:

68Q45 | Formal languages and automata |

68Q42 | Grammars and rewriting systems |

68Q19 | Descriptive complexity and finite models |

##### 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
PDF
BibTeX
XML
Cite

\textit{S. C. Reghizzi} and \textit{P. San Pietro}, RAIRO, Theor. Inform. Appl. 45, No. 1, 77--97 (2011; Zbl 1219.68112)

**OpenURL**

##### References:

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

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

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

[4] | M. Jantzen, On the hierarchy of Petri net languages. ITA13 (1979). · 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. |

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

[7] | A. Salomaa, Theory of Automata. Pergamon Press, Oxford (1969). · 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. · Zbl 0813.68129 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.