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

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

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

(19)

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

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)