Families of locally testable languages

DOI10.1016/S0304-3975(98)00332-6zbMath0944.68097WikidataQ127740389 ScholiaQ127740389MaRDI QIDQ1575558

Pascal Caron

Publication date: 21 August 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

algorithmsautomataregular languageslocally testable languages

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05)

Related Items

Unnamed Item ⋮ Beyond operator-precedence grammars and languages ⋮ On the descriptional complexity of stateless deterministic ordered restarting automata ⋮ Unnamed Item ⋮ STRICT LOCAL TESTABILITY WITH CONSENSUS EQUALS REGULARITY, AND OTHER PROPERTIES ⋮ SHUFFLE DECOMPOSITIONS OF REGULAR LANGUAGES ⋮ Two-Sided Strictly Locally Testable Languages ⋮ Execution monitoring enforcement under memory-limitation constraints ⋮ Reducing the time complexity of testing for local threshold testability ⋮ Non-erasing Chomsky-Schützenberger theorem with grammar-independent alphabet ⋮ FROM REGULAR TO STRICTLY LOCALLY TESTABLE LANGUAGES ⋮ LANGAGE: A Maple package for automaton characterization of regular languages ⋮ On Some Decision Problems for Stateless Deterministic Ordered Restarting Automata

Uses Software

• LANGAGE
• AG

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Local languages and the Berry-Sethi algorithm
• Codes circulaires, automates locaux et entropie
• Languages and scanners
• Transductions des langages de Chomsky
• Locally testable languages
• Characterizations of locally testable events
• A characterization of strictly locally testable languages and its application to subsemigroups of a free semigroup
• Algebraic decision procedures for local testability
• A polynomial time algorithm for the local testability problem of deterministic finite automata