# Consensual languages and matching finite-state computations

Stefano Crespi Reghizzi; Pierluigi San Pietro

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2011)

- Volume: 45, Issue: 1, page 77-97
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topCrespi Reghizzi, Stefano, and San Pietro, Pierluigi. "Consensual languages and matching finite-state computations." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 45.1 (2011): 77-97. <http://eudml.org/doc/272992>.

@article{CrespiReghizzi2011,

abstract = {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.},

author = {Crespi Reghizzi, Stefano, San Pietro, Pierluigi},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

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},

language = {eng},

number = {1},

pages = {77-97},

publisher = {EDP-Sciences},

title = {Consensual languages and matching finite-state computations},

url = {http://eudml.org/doc/272992},

volume = {45},

year = {2011},

}

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

PB - EDP-Sciences

VL - 45

IS - 1

SP - 77

EP - 97

AB - 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.

LA - eng

KW - formal languages; finite automata; consensual languages; counter machines; polynomial time parsing; non-semilinear languages; Parikh mapping; descriptive complexity of regular languages; degree of grammaticality

UR - http://eudml.org/doc/272992

ER -

## References

top- [1] A.K. Chandra, D. Kozen and L.J. Stockmeyer, Alternation. J. ACM28 (1981) 114–133. Zbl0473.68043MR603186
- [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.68452MR2540324
- [3] S. Crespi Reghizzi and P. San Pietro, Languages defined by consensual computations. in ICTCS09 (2009). Zbl1219.68112
- [4] M. Jantzen, On the hierarchy of Petri net languages. ITA 13 (1979). Zbl0404.68076MR525455
- [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. MR1470019
- [6] M. Minsky, Computation: Finite and Infinite Machines. Prentice-Hall, Englewood Cliffs (1976). Zbl0195.02402MR356580
- [7] A. Salomaa, Theory of Automata. Pergamon Press, Oxford (1969). Zbl0193.32901MR262021
- [8] K. Vijay-Shanker and D.J. Weir, The equivalence of four extensions of context-free grammars. Math. Syst. Theor.27 (1994) 511–546. Zbl0813.68129MR1288685

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.