FROM REGULAR TO STRICTLY LOCALLY TESTABLE LANGUAGES

DOI10.1142/S0129054112400710zbMath1290.68069OpenAlexW1998361452MaRDI QIDQ2841978

Stefano Crespi Reghizzi, Pierluigi San Pietro

Publication date: 30 July 2013

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054112400710

zbMATH Keywords

regular languageshomomorphic characterizationfactor decodabilityMedvedev theoremstrictly locally testable languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (6)

Reducing local alphabet size in recognizable picture languages ⋮ Reducing the local alphabet size in tiling systems by means of 2D comma-free codes ⋮ Homomorphic characterization of tree languages based on comma-free encoding ⋮ STRICT LOCAL TESTABILITY WITH CONSENSUS EQUALS REGULARITY, AND OTHER PROPERTIES ⋮ Non-erasing Chomsky-Schützenberger theorem with grammar-independent alphabet ⋮ The alphabetic complexity in homomorphic definitions of word, tree and picture languages

Cites Work

• Local languages and the Berry-Sethi algorithm
• Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors
• Families of locally testable languages
• Consensual languages and matching finite-state computations
• A characterization of strictly locally testable languages and its application to subsemigroups of a free semigroup

This page was built for publication: FROM REGULAR TO STRICTLY LOCALLY TESTABLE LANGUAGES