A characterization of strictly locally testable languages and its application to subsemigroups of a free semigroup

Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items (25)

Star-free sets of integers ⋮ Transductions and the parallel generation of languages^† ⋮ The syntactic monoid of hairpin-free languages ⋮ Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors ⋮ On the splicing operation ⋮ Simple splicing systems ⋮ Reducing the local alphabet size in tiling systems by means of 2D comma-free codes ⋮ Relativized adjacency ⋮ Codes and local constraints ⋮ A synchronization property of pure subsemigroups of a free semigroup ⋮ WATSON-CRICK BORDERED WORDS AND THEIR SYNTACTIC MONOID ⋮ STRICT LOCAL TESTABILITY WITH CONSENSUS EQUALS REGULARITY, AND OTHER PROPERTIES ⋮ Two-Sided Strictly Locally Testable Languages ⋮ Regular splicing languages and subclasses ⋮ Linear splicing and syntactic monoid ⋮ Pseudo-cyclic renewal systems ⋮ A conjugacy invariant for reducible sofic shifts and its semigroup characterizations ⋮ Splicing representations of stricly locally testable languages ⋮ On the bound of the synchronization delay of a local automaton ⋮ THE SYNTACTIC GRAPH OF A SOFIC SHIFT IS INVARIANT UNDER SHIFT EQUIVALENCE ⋮ Cyclic renewal systems ⋮ Families of locally testable languages ⋮ FROM REGULAR TO STRICTLY LOCALLY TESTABLE LANGUAGES ⋮ Right and left locally testable languages ⋮ Existence of constants in regular splicing languages

This page was built for publication: A characterization of strictly locally testable languages and its application to subsemigroups of a free semigroup