Piecewise testable tree languages

DOI10.2168/LMCS-8(3:26)2012MaRDI QIDQ3166216zbMATH OpenOpenAlexFDO

Authors Mikołaj Bojańczyk, Luc Segoufin, Howard Straubing

Publication date 22 October 2012

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1208.5129

zbMATH Keywords

decidabilitydefinabilityfirst-order logic on treespiecewise testabilitysyntactic algebrastree languagesunranked trees

Mathematics Subject Classification ID

Logic in computer science (03B70) Automata and formal grammars in connection with logical questions (03D05) Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Abstract: This paper presents a decidable characterization of tree languages that can be defined by a boolean combination of Sigma_1 sentences. This is a tree extension of the Simon theorem, which says that a string language can be defined by a boolean combination of Sigma_1 sentences if and only if its syntactic monoid is J-trivial.

Recommendations

• A Decidable Characterization of Locally Testable Tree Languages
• A decidable characterization of locally testable tree languages
• Piecewise testable languages via combinatorics on words
• A proof of Simon's theorem on piecewise testable languages
• An algebraic characterization of frontier testable tree languages

Cited in

(27)

• A proof of Simon's theorem on piecewise testable languages
• Separability by piecewise testable languages is \textsc{PTime}-complete
• Computation tree measurement language (CTML)
• Automata on finite trees
• Algebra for trees
• Property testing of regular tree languages
• Wreath products of forest algebras, with applications to tree logics
• EF+EX forest algebras
• A Note on Decidable Separability by Piecewise Testable Languages
• The mu-calculus and Model Checking
• A decidable characterization of locally testable tree languages
• Characterization of Logics over Ranked Tree Languages
• Forest Expressions
• A Decidable Characterization of Locally Testable Tree Languages
• Partially ordered automata and piecewise testability
• Some classes of sets of structures definable without quantifiers
• The height of piecewise-testable languages with applications in logical complexity
• scientific article; zbMATH DE number 7056230 (Why is no real title available?)
• Fragments of first-order logic over infinite words
• STACS 2005
• Weak separation problem for tree languages
• On Arch Factorization and Subword Universality for Words and Compressed Words
• Aperiodicity, Star-freeness, and First-order Logic Definability of Operator Precedence Languages
• Piecewise testable languages via combinatorics on words
• An algebraic characterization of frontier testable tree languages
• On the piecewise complexity of words
• A complexity approach to tree algebras: the bounded case

This page was built for publication: Piecewise testable tree languages

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