First-order separation over countable ordinals

DOI10.1007/978-3-030-99253-8_14MaRDI QIDQ6181932zbMATH OpenFDO

Authors

Publication date 23 January 2024

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2201.03089

zbMATH Keywords

countable ordinalsfirst-order logicmonadic second-order logicpointlike setsregular languagesseparation

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Abstract: We show that the existence of a first-order formula separating two monadic second order formulas over countable ordinal words is decidable. This extends the work of Henckell and Almeida on finite words, and of Place and Zeitoun on $omega$-words. For this, we develop the algebraic concept of monoid (resp. $omega$-semigroup, resp. ordinal monoid) with aperiodic merge, an extension of monoids (resp. $omega$-semigroup, resp. ordinal monoid) that explicitly includes a new operation capturing the loss of precision induced by first-order indistinguishability. We also show the computability of FO-pointlike sets, and the decidability of the covering problem for first-order logic on countable ordinal words.

Recommendations

• Separating regular languages with first-order logic
• Separating regular languages with first-order logic
• First-order definable languages
• Complexity of counting first-order logic for the subword order
• Regular languages of words over countable linear orderings

Cites work

• Algebraic characterization of FO for scattered linear orderings
• Algorithmic uses of the Feferman-Vaught theorem
• An algebraic approach to MSO-definability on countable linear orderings
• AN ALGEBRAIC THEORY FOR REGULAR LANGUAGES OF FINITE AND INFINITE WORDS
• COMPLEMENTATION OF RATIONAL SETS ON COUNTABLE SCATTERED LINEAR ORDERINGS
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Finite automata and ordinals
• Finite automata, definable sets, and regular expressions over \(\omega^n\)- tapes
• First-order logic and its infinitary quantifier extensions over countable words
• Going Higher in First-Order Quantifier Alternation Hierarchies on Words
• scientific article; zbMATH DE number 3881897 (Why is no real title available?)
• scientific article; zbMATH DE number 3915652 (Why is no real title available?)
• scientific article; zbMATH DE number 3924161 (Why is no real title available?)
• scientific article; zbMATH DE number 1189233 (Why is no real title available?)
• scientific article; zbMATH DE number 3767656 (Why is no real title available?)
• scientific article; zbMATH DE number 3495598 (Why is no real title available?)
• scientific article; zbMATH DE number 1304310 (Why is no real title available?)
• scientific article; zbMATH DE number 2206109 (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?)
• INEVITABLE GRAPHS: A PROOF OF THE TYPE II CONJECTURE AND SOME RELATED DECISION PROCEDURES
• Limited set quantifiers over countable linear orderings
• Logic over words on denumerable ordinals
• Merge decompositions, two-sided Krohn-Rhodes, and aperiodic pointlikes
• On finite monoids having only trivial subgroups
• Pointlike sets for varieties determined by groups
• Pointlike sets: the finest aperiodic cover of a finite semigroup
• Recognisable languages over monads
• Schützenberger and Eilenberg theorems for words on linear orderings
• Separating regular languages with first-order logic
• Separation for dot-depth two
• Some algorithmic problems for pseudovarieties
• The covering problem
• The monadic theory of order
• The pseudovariety J is hyperdecidable
• Two-Variable Logic over Countable Linear Orderings

This page was built for publication: First-order separation over countable ordinals

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