Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-18T02:46:14.243Z Has data issue: false hasContentIssue false

Consensual languages and matching finite-state computations

Published online by Cambridge University Press:  15 March 2011

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

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Copyright
© EDP Sciences, 2011