Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-22T23:31:15.744Z Has data issue: false hasContentIssue false
  • English
  • Français

Consensual languages and matching finite-state computations

Published online by Cambridge University Press:  15 March 2011

Stefano Crespi Reghizzi  and
Pierluigi San Pietro
Stefano Crespi Reghizzi
Affiliation:
Dipartimento di Elettronica e Informazione, Politecnico di Milano, Piazza Leonardo da Vinci, 32, 20133 Milano, Italy; {crespi;sanpietro}@elet.polimi.it
Pierluigi San Pietro
Affiliation:
Dipartimento di Elettronica e Informazione, Politecnico di Milano, Piazza Leonardo da Vinci, 32, 20133 Milano, Italy; {crespi;sanpietro}@elet.polimi.it
Get access

Abstract

An ever present, common sense idea in language modelling research is that, for aword to be a valid phrase, it should comply with multiple constraints atonce. A new language definition model is studied, based on agreement or consensusbetween similar strings. Considering a regular set of strings over a bipartitealphabet made by pairs of unmarked/marked symbols, a match relation isintroduced, in order to specify when such strings agree. Then a regular setover the bipartite alphabet can be interpreted as specifying another languageover the unmarked alphabet, called the consensual language. A word is in theconsensual language if a set of corresponding matching strings is in theoriginal language. The family thus defined includes the regular languages andalso interesting non-semilinear ones. The word problem can be solved inNLOGSPACE, hence in P time. The emptiness problem is undecidable. Closure properties areproved for intersection with regular sets and inverse alphabetical homomorphism.Several conditions for a consensual definition to yield a regular language arepresented, and it is shown that the size of a consensual specification ofregular languages can be in a logarithmic ratio with respect to a DFA. Thefamily is incomparable with context-free and tree-adjoining grammar families.

Keywords

Formal languagesfinite automataconsensual languagescounter machinespolynomial timeparsingnon-semilinear languagesParikh mappingdescriptive complexity of regular languagesdegree of grammaticality
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 45 , Issue 1: ICTCS 09 , January 2011 , pp. 77 - 97
Copyright
© EDP Sciences, 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Chandra, A.K., Kozen, D. and Stockmeyer, L.J., Alternation. J. ACM 28 (1981) 114–133. CrossRef
Crespi Reghizzi, S. and San Pietro, P., Consensual definition of languages by regular sets, in LATA. Lecture Notes in Computer Science 5196 (2008) 196–208. CrossRef
S. Crespi Reghizzi and P. San Pietro, Languages defined by consensual computations. in ICTCS09 (2009).
M. Jantzen, On the hierarchy of Petri net languages. ITA 13 (1979).
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).
A. Salomaa, Theory of Automata. Pergamon Press, Oxford (1969).
Vijay-Shanker, K. and Weir, D.J., The equivalence of four extensions of context-free grammars. Math. Syst. Theor. 27 (1994) 511–546. CrossRef