STRICT LOCAL TESTABILITY WITH CONSENSUS EQUALS REGULARITY, AND OTHER PROPERTIES

DOI10.1142/S0129054113400169zbMath1408.68094OpenAlexW2033706835MaRDI 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

zbMATH Keywords

regular languageformal languagescontext-sensitiveconsensual languagecontext-freehomomorphic characterizationMedvedev theoremnon-countingstrict local testability

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (1)

Counter machines, Petri nets, and consensual computation

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

This page was built for publication: STRICT LOCAL TESTABILITY WITH CONSENSUS EQUALS REGULARITY, AND OTHER PROPERTIES