Regular tree languages definable in FO and in FO_mod

DOI10.1145/1614431.1614435zbMATH Open1351.68134OpenAlexW2012552318MaRDI QIDQ2946590FDOQ2946590

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

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

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)

Cited In (17)

• Deciding definability in \(\mathrm{FO}^2(<_{\mathbf{v}},<_{\mathbf{h}})\) on trees
• A Note on Decidable Separability by Piecewise Testable Languages
• Deciding twig-definability of node selecting tree automata
• 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
• Title not available (Why is that?)
• Theoretical computer science: computational complexity
• STACS 2005
• 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
• Title not available (Why is that?)

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)