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

congruencesmonoidsregular languagessemiautomatastar-free languages

Mathematics Subject Classification ID

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

Review text

This paper discusses a family of star-free languages, over a two letter alphabet, which generalizes both the locally testable languages and the \({\mathcal G}\)-trivial languages. Characterizations are given in terms of congruences, monoids, and semiautomata.

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

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

Cited in

(15)

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

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)