STRICT LOCAL TESTABILITY WITH CONSENSUS EQUALS REGULARITY, AND OTHER PROPERTIES
From MaRDI portal
Publication:5401553
DOI10.1142/S0129054113400169zbMath1408.68094MaRDI QIDQ5401553
Pierluigi San Pietro, Stefano Crespi Reghizzi
Publication date: 10 March 2014
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0129054113400169
regular language; formal languages; context-sensitive; consensual language; context-free; homomorphic characterization; Medvedev theorem; non-counting; strict local testability
68Q45: Formal languages and automata
Related Items
Cites Work
- Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors
- Families of locally testable languages
- FROM REGULAR TO STRICTLY LOCALLY TESTABLE LANGUAGES
- A characterization of strictly locally testable languages and its application to subsemigroups of a free semigroup