Regular tree languages definable in FO and in FO_mod

DOI10.1145/1614431.1614435MaRDI QIDQ2946590zbMATH OpenOpenAlexFDO

Authors Michael Benedikt, Luc Segoufin

Publication date 17 September 2015

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1614431.1614435

zbMATH Keywords

first-order logicregular tree languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Recommendations

• STACS 2005
• First-order logic on finite trees
• Modulo-counting quantifiers over finite trees
• Regular tree languages, cardinality predicates, and addition-invariant FO
• First-order properties of trees, star-free expressions, and aperiodicity

Cited in

(17)

• scientific article; zbMATH DE number 2206362 (Why is no real title available?)
• Deciding definability in \(\mathrm{FO}^2(<_{\mathbf{v}},<_{\mathbf{h}})\) on trees
• Deciding twig-definability of node selecting tree automata
• A Note on Decidable Separability by Piecewise Testable Languages
• EF+EX forest algebras
• Regularity equals monadic second-order definability for quasi-trees
• Regular tree languages, cardinality predicates, and addition-invariant FO
• Automata on finite trees
• scientific article; zbMATH DE number 4108163 (Why is no real title available?)
• STACS 2005
• Theoretical computer science: computational complexity
• Two-variable first order logic with modular predicates over words
• The mu-calculus and Model Checking
• On the locality of arb-invariant first-order formulas with modulo counting quantifiers
• On the expressive power of FO[+]
• Algebra for trees
• Modulo counting on words and trees

This page was built for publication: Regular tree languages definable in FO and in FO\(_{\mathrm{mod}}\)

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