On generalized locally testable languages

DOI10.1016/0012-365X(84)90045-1MaRDI QIDQ760215zbMATH OpenOpenAlexFDO

Authors Janusz Brzozowski, Faith E. Fich

Publication date 1984

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(84)90045-1

zbMATH Keywords

congruencesregular languagesmonoidsstar-free languagessemiautomata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Semigroups in automata theory, linguistics, etc. (20M35)

Recommendations

• Some variations on the notion of locally testable language
• From regular to strictly locally testable languages
• From regular to strictly locally testable languages
• Families of locally testable languages
• On two-sided locally testable languages
• scientific article; zbMATH DE number 2050939
• scientific article; zbMATH DE number 1507233
• Two-Sided Strictly Locally Testable Languages
• On separation by locally testable and locally threshold testable languages
• Measuring power of locally testable languages

Cites work

• scientific article; zbMATH DE number 3561239 (Why is no real title available?)
• scientific article; zbMATH DE number 3640907 (Why is no real title available?)
• A generalization of finiteness
• Algebraic decision procedures for local testability
• Characterizations of locally testable events
• Languages of R-trivial monoids

Cited in

(15)

• Complete κ-reducibility of pseudovarieties of the form DRH
• Strongly locally testable semigroups with commuting idempotents and related languages
• Two-Sided Strictly Locally Testable Languages
• Some results on the dot-depth hierarchy
• Graph congruences and pair testing
• Profinite categories and semidirect products
• A Testing Theory for a Higher-Order Cryptographic Language
• Local testability from words to traces, a suitable definition
• Locally countable pseudovarieties
• Right and left strongly locally testable semigroups and languages
• On separation by locally testable and locally threshold testable languages
• Fragments of first-order logic over infinite words
• STRICT LOCAL TESTABILITY OF THE FINITE CONTROL OF TWO-WAY AUTOMATA AND OF REGULAR PICTURE DESCRIPTION LANGUAGES
• scientific article; zbMATH DE number 3881894 (Why is no real title available?)
• On a conjecture concerning dot-depth two languages

This page was built for publication: On generalized locally testable languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q760215)