Consiglio Nazionale delle Ricerche

Tipo di prodottoArticolo in rivista
TitoloStrict local testability with consensus equals regularity, and other properties
Anno di pubblicazione2013
Formato
  • Elettronico
  • Cartaceo
Autore/iCrespi Reghizzi, Stefano ; San Pietro, Pierluigi
Affiliazioni autoriPolitecnico di Milano; Consiglio Nazionale delle Ricerche
Autori CNR e affiliazioni
  • STEFANO CRESPI REGHIZZI
  • PIERLUIGI SAN PIETRO
Lingua/e
  • inglese
AbstractA recent language definition device named consensual is based on agreement between similar words. Considering a language over a bipartite alphabet made by pairs of unmarked/marked letters, the match relation specifies when such words agree. Thus a set (the "base") over the bipartite alphabet consensually specifies another language that includes any terminal word such that a set of corresponding matching words is in the base. We show that all and only the regular languages are consensually generated by a strictly locally testable base; the result is based on a generalization of Medvedev's homomorphic characterization of regular languages. Consensually context-free languages strictly include the base family. The consensual and the base families collapse together if the base is context-sensitive. © 2013 World Scientific Publishing Company.
Lingua abstractinglese
Altro abstract-
Lingua altro abstract-
Pagine da747
Pagine a763
Pagine totali17
RivistaInternational journal of foundations of computer science
Attiva dal 1990
Editore: World Scientific. - Singapore
Paese di pubblicazione: Singapore
Lingua: inglese
ISSN: 0129-0541
Titolo chiave: International journal of foundations of computer science
Titolo abbreviato: Int. j. found. comput. sci.
Numero volume della rivista24
Fascicolo della rivista6
DOI10.1142/S0129054113400169
Verificato da refereeSì: Internazionale
Stato della pubblicazionePublished version
Indicizzazione (in banche dati controllate)
  • ISI Web of Science (WOS) (Codice:000329121500005)
  • Scopus (Codice:2-s2.0-84891426344)
Parole chiaveconsensual language, context-free, context-sensitive, Formal languages, homomorphic characterization, Medvedev theorem, non-counting, regular language, strict local testability
Link (URL, URI)http://www.scopus.com/record/display.url?eid=2-s2.0-84891426344&origin=inward
Titolo parallelo-
Data di accettazione-
Note/Altre informazioni-
Strutture CNR
  • IEIIT — IEIIT - Sede secondaria di Milano
Moduli CNR-
Progetti Europei-
Allegati
  • Full pdf of the paper, original from the publisher