Modulo-counting quantifiers over finite trees

DOI10.1016/0304-3975(94)90270-4MaRDI QIDQ1325850zbMATH OpenOpenAlexFDO

Authors Andreas Potthoff

Publication date 3 November 1994

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(94)90270-4

zbMATH Keywords

first-order logiclogical definability of tree languagesmodulo-counting quantifiersmonadic second-order logic

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Regular tree languages definable in FO and in FO\(_{\mathrm{mod}}\)
• First-order logic on finite trees
• Modulo counting on words and trees
• Trace languages definable with modular quantifiers
• Extending two-variable logic on trees

Cites work

• A Note on Star-Free Events
• An application of games to the completeness problem for formalized theories
• Classifying regular events in symbolic logic
• Decision Problems of Finite Automata Design and Related Arithmetics
• First-order properties of trees, star-free expressions, and aperiodicity
• Generalized finite automata theory with an application to a decision problem of second-order logic
• scientific article; zbMATH DE number 3885853 (Why is no real title available?)
• scientific article; zbMATH DE number 3888931 (Why is no real title available?)
• scientific article; zbMATH DE number 4076666 (Why is no real title available?)
• scientific article; zbMATH DE number 3767656 (Why is no real title available?)
• scientific article; zbMATH DE number 3550662 (Why is no real title available?)
• scientific article; zbMATH DE number 3615891 (Why is no real title available?)
• scientific article; zbMATH DE number 522865 (Why is no real title available?)
• scientific article; zbMATH DE number 1995181 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• On finite monoids having only trivial subgroups
• Tree acceptors and some of their applications
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(15)

• Inessential features, ineliminable features, and modal logics for model theoretic syntax
• Towards a language theory for infinite N-free pomsets.
• Algebra for trees
• Regular tree languages, cardinality predicates, and addition-invariant FO
• Regular tree languages definable in FO and in FO\(_{\mathrm{mod}}\)
• Aperiodicity in Tree Automata
• Games for Temporal Logics on Trees
• Cardinality Quantifiers in MLO over Trees
• scientific article; zbMATH DE number 1042660 (Why is no real title available?)
• scientific article; zbMATH DE number 1389856 (Why is no real title available?)
• First-order logic on finite trees
• Modulo counting on words and trees
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• Trace languages definable with modular quantifiers
• Aperiodicity, Star-freeness, and First-order Logic Definability of Operator Precedence Languages

This page was built for publication: Modulo-counting quantifiers over finite trees

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