scientific article; zbMATH DE number 512866

MaRDI QIDQ4281563zbMATH OpenFDO

Authors Thomas Wilke

Publication date 10 March 1994

zbMATH Keywords

decidabilityinfinite wordslocally threshold testable \(\omega\)- languages

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Formal languages and automata (68Q45)

Recommendations

• Locally finite languages
• A decidable characterization of locally testable tree languages
• A Decidable Characterization of Locally Testable Tree Languages
• Families of locally testable languages

Cited in

(14)

• A generalization of Cobham's theorem to automata over real numbers
• Level two of the quantifier alternation hierarchy over infinite words
• Expressive power of existential first-order sentences of Büchi's sequential calculus
• Logic, semigroups and automata on words
• Refuting learning revisited.
• On the Sets of Real Numbers Recognized by Finite Automata in Multiple Bases
• Infinite and bi-infinite words with decidable monadic theories
• Extensions of -regular languages
• A Generalization of Semenov’s Theorem to Automata over Real Numbers
• Infinite and bi-infinite words with decidable monadic theories
• Level Two of the Quantifier Alternation Hierarchy over Infinite Words
• Locally finite languages
• Reducing the time complexity of testing for local threshold testability
• On decidability properties of local sentences

This page was built for publication:

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