Piecewise testable tree languages
From MaRDI portal
Publication:3166216
DOI10.2168/LMCS-8(3:26)2012zbMath1261.03126arXiv1208.5129MaRDI 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
decidability; definability; tree languages; syntactic algebras; unranked trees; first-order logic on trees; piecewise testability
68Q45: Formal languages and automata
03B70: Logic in computer science
03D05: Automata and formal grammars in connection with logical questions
68Q70: Algebraic theory of languages and automata
Related Items
Unnamed Item, Unnamed Item, 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, Fragments of first-order logic over infinite words, Separability by piecewise testable languages is \textsc{PTime}-complete, Automata on finite trees, Algebra for trees, EF+EX Forest Algebras, A Note on Decidable Separability by Piecewise Testable Languages, The mu-calculus and Model Checking, Characterization of Logics over Ranked Tree Languages