Regular languages of thin trees

DOI10.1007/S00224-014-9595-ZMaRDI QIDQ290908zbMATHOpenAlexDBLPWikidataFDO

Authors Tomasz Idziaszek, Michał Skrzypczak, Mikołaj Bojańczyk

Publication date 3 June 2016

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2013/3965/

zbMATH Keywords

topological complexityregular languageseffective characterizationsinfinite trees

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Regular languages of thin trees
• Regular tree languages in low levels of the Wadge hierarchy
• Regular tree languages and quasi orders
• STACS 2005
• Publication:4847003
• On regular tree languages and deterministic pushdown automata
• Publication:3365845
• Nondeterministic tree width of regular languages
• Algebraic recognizability of regular tree languages
• A Characterisation of Pi^0_2 Regular Tree Languages

Cites work

• scientific article; zbMATH DE number 6680130 (Why is no real title available?)
• scientific article; zbMATH DE number 5872386 (Why is no real title available?)
• scientific article; zbMATH DE number 3751028 (Why is no real title available?)
• scientific article; zbMATH DE number 3495598 (Why is no real title available?)
• scientific article; zbMATH DE number 1304310 (Why is no real title available?)
• scientific article; zbMATH DE number 722611 (Why is no real title available?)
• scientific article; zbMATH DE number 1775408 (Why is no real title available?)
• scientific article; zbMATH DE number 2206109 (Why is no real title available?)
• scientific article; zbMATH DE number 3237829 (Why is no real title available?)
• A gap property of deterministic tree languages.
• AN ALGEBRAIC THEORY FOR REGULAR LANGUAGES OF FINITE AND INFINITE WORDS
• Algebra for Infinite Forests with an Application to the Temporal Logic EF
• Around dot-depth one
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Interpretations in trees with countably many branches
• On finite monoids having only trivial subgroups
• On recognizable tree languages beyond the Borel hierarchy
• On the Borel inseparability of game tree languages
• Recognisability for algebras of infinite trees
• Regular languages of infinite trees that are Boolean combinations of open sets
• The Borel hierarchy is infinite in the class of regular sets of trees
• The Wadge Hierarchy of Deterministic Tree Languages
• Uniformization and skolem functions in the class of trees

Cited in

(10)

• Regular tree languages in low levels of the Wadge hierarchy
• Regular languages of thin trees
• scientific article; zbMATH DE number 7215285 (Why is no real title available?)
• Sequences with increasing subsequence
• Relatively regular languages and thin codes
• Algebra for trees
• scientific article; zbMATH DE number 5251101 (Why is no real title available?)
• scientific article; zbMATH DE number 5005936 (Why is no real title available?)
• A non-regular language of infinite trees that is recognizable by a sort-wise finite algebra
• scientific article; zbMATH DE number 522865 (Why is no real title available?)

This page was built for publication: Regular languages of thin trees

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