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

Abstract

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

How to cite

top

Crespi 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
  1. A.K. Chandra, D. Kozen and L.J. Stockmeyer, Alternation. J. ACM28 (1981) 114–133.  
  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.  
  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. ITA13 (1979).  
  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).  
  7. A. Salomaa, Theory of Automata. Pergamon Press, Oxford (1969).  
  8. K. Vijay-Shanker and D.J. Weir, The equivalence of four extensions of context-free grammars. Math. Syst. Theor.27 (1994) 511–546.  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.