Limited set quantifiers over countable linear orderings

DOI10.1007/978-3-662-47666-6_12MaRDI QIDQ3449472zbMATH OpenOpenAlexFDO

Authors Thomas Colcombet, A. V. Sreejith

Publication date 4 November 2015

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-47666-6_12

zbMATH Keywords

monadic second-order logiclinear orderingsalgebraic characterization

Mathematics Subject Classification ID

Higher-order logic (03B16) Decidability of theories and sets of sentences (03B25) Total orders (06A05)

Recommendations

• Two-Variable Logic over Countable Linear Orderings
• An algebraic approach to MSO-definability on countable linear orderings
• scientific article; zbMATH DE number 1163934
• Two-variable logic with counting and a linear order
• Regular languages of words over countable linear orderings

Cites work

• scientific article; zbMATH DE number 3767656 (Why is no real title available?)
• scientific article; zbMATH DE number 3237829 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• Algebraic characterization of FO for scattered linear orderings
• COMPLEMENTATION OF RATIONAL SETS ON COUNTABLE SCATTERED LINEAR ORDERINGS
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Definability and undefinability with real order at the background
• On finite monoids having only trivial subgroups
• Regular languages of words over countable linear orderings
• Testing and generating infinite sequences by a finite automaton
• The monadic theory of order

Cited in

(6)

• Monadic theory of a linear order versus the theory of its subsets with the lifted min/max operations
• Definability in Rationals with Real Order in the Background
• scientific article; zbMATH DE number 68156 (Why is no real title available?)
• First-order logic and its infinitary quantifier extensions over countable words
• First-order separation over countable ordinals
• Algebraic characterizations and block product decompositions for first order logic and its infinitary quantifier extensions over countable words

This page was built for publication: Limited set quantifiers over countable linear orderings

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