Piecewise testable tree languages
From MaRDI portal
Publication:3166216
DOI10.2168/LMCS-8(3:26)2012zbMath1261.03126arXiv1208.5129OpenAlexW1965525337MaRDI QIDQ3166216
Luc Segoufin, Mikołaj Bojańczyk, 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
decidabilitydefinabilitytree languagessyntactic algebrasunranked treesfirst-order logic on treespiecewise testability
Formal languages and automata (68Q45) Logic in computer science (03B70) Automata and formal grammars in connection with logical questions (03D05) Algebraic theory of languages and automata (68Q70)
Related Items (13)
The mu-calculus and Model Checking ⋮ EF+EX Forest Algebras ⋮ A Note on Decidable Separability by Piecewise Testable Languages ⋮ Unnamed Item ⋮ On Arch Factorization and Subword Universality for Words and Compressed Words ⋮ Aperiodicity, Star-freeness, and First-order Logic Definability of Operator Precedence Languages ⋮ Separability by piecewise testable languages is \textsc{PTime}-complete ⋮ Characterization of Logics over Ranked Tree Languages ⋮ Fragments of first-order logic over infinite words ⋮ Unnamed Item ⋮ Automata on finite trees ⋮ Algebra for trees ⋮ Weak Separation Problem for Tree Languages
This page was built for publication: Piecewise testable tree languages
