# Consensual languages and matching finite-state computations

Stefano Crespi Reghizzi; Pierluigi San Pietro

RAIRO - Theoretical Informatics and 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 45.1 (2011): 77-97. <http://eudml.org/doc/222057>.

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

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; formal languages; polynomial time parsing},

language = {eng},

month = {3},

number = {1},

pages = {77-97},

publisher = {EDP Sciences},

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

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

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

DA - 2011/3//

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; formal languages; polynomial time parsing

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

ER -

## References

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

## NotesEmbed ?

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