Abstract
We contribute to the refined understanding of the language-logic-algebra interplay in the context of first-order properties of countable words. We establish decidable algebraic characterizations of one variable fragment of FO as well as boolean closure of existential fragment of FO via a strengthening of Simon’s theorem about piecewise testable languages. We propose a new extension of FO which admits infinitary quantifiers to reason about the inherent infinitary properties of countable words. We provide a very natural and hierarchical block-product based characterization of the new extension. We also explicate its role in view of other natural and classical logical systems such as WMSO and FO[cut] - an extension of FO where quantification over Dedekind-cuts is allowed. We also rule out the possibility of a finite-basis for a block-product based characterization of these logical systems. Finally, we report simple but novel algebraic characterizations of one variable fragments of the hierarchies of the new proposed extension of FO.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Here J is one of the fundamental Green’s equivalence relations.
- 2.
Henceforth, by a slight abuse of notation,
,
,
also denote the language-classes defined by the corresponding logics. - 3.
This simply means that the underlying monoid of a
is aperiodic.
References
Adsul, B., Sarkar, S., Sreejith, A.V.: Block products for algebras over countable words and applications to logic. In: 34th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2019, pp. 1–13. IEEE (2019)
Adsul, B., Sarkar, S., Sreejith, A.V.: First-order logic and its infinitary quantifier extensions over countable words. CoRR abs/2107.01468 (2021). https://arxiv.org/abs/2107.01468
Baudisch, A., Seese, D., Tuschik, H.P., Weese, M.: Decidability and Generalized Quantifiers. Akademie Verlag, Berlin (1980)
Bès, A., Carton, O.: Algebraic characterization of FO for scattered linear orderings. In: Computer Science Logic, 20th Annual Conference of the EACSL, CSL 2011. LIPIcs, vol. 12, pp. 67–81. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2011)
Carton, O., Colcombet, T., Puppis, G.: An algebraic approach to MSO-definability on countable linear orderings. J. Symb. Log. 83(3), 1147–1189 (2018)
Colcombet, T., Sreejith, A.V.: Limited set quantifiers over countable linear orderings. In: Halldórsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9135, pp. 146–158. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47666-6_12
Diekert, V., Gastin, P., Kufleitner, M.: A survey on small fragments of first-order logic over finite words. Int. J. Found. Comput. Sci. 19(3), 513–548 (2008)
Gabbay, D.M., Hodkinson, I., Reynolds, M.: Temporal Logic: Mathematical Foundations and Computational Aspects, vol. 1. Oxford University Press, Oxford (1994)
Gradel, E., Otto, M., Rosen, E.: Two-variable logic with counting is decidable. In: Proceedings of Twelfth Annual IEEE Symposium on Logic in Computer Science, pp. 306–317 (1997)
Manuel, A., Sreejith, A.V.: Two-variable logic over countable linear orderings. In: 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, pp. 66:1–66:13 (2016)
Pin, J.E.: Handbook of Formal Languages, Vol. 1. chap. Syntactic Semigroups, pp. 679–746. Springer-Verlag, Heidelberg (1997)
Pin, J.É.: Mathematical foundations of automata theory (2020)
Rosenstein, J.G.: Linear Orderings. Academic Press, New York (1981)
Simon, I.: Piecewise testable events. In: Brakhage, H. (ed.) GI-Fachtagung 1975. LNCS, vol. 33, pp. 214–222. Springer, Heidelberg (1975). https://doi.org/10.1007/3-540-07407-4_23
Straubing, H.: Finite automata, formal logic, and circuit complexity. Birkhauser Verlag, Basel, Switzerland (1994)
Straubing, H., Thérien, D., Thomas, W.: Regular languages defined with generalized quantifiers. In: Lepistö, T., Salomaa, A. (eds.) ICALP 1988. LNCS, vol. 317, pp. 561–575. Springer, Heidelberg (1988). https://doi.org/10.1007/3-540-19488-6_142
Straubing, H., Weil, P.: Varieties. CoRR abs/1502.03951 (2015). http://arxiv.org/abs/1502.03951
Thomas, W.: Handbook of Formal Languages, vol. 3. chap. Languages, Automata, and Logic, pp. 389–455. Springer-Verlag Inc., New York (1997). http://dl.acm.org/citation.cfm?id=267871.267878
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Adsul, B., Sarkar, S., Sreejith, A.V. (2021). First-Order Logic and Its Infinitary Quantifier Extensions over Countable Words. In: Bampis, E., Pagourtzis, A. (eds) Fundamentals of Computation Theory. FCT 2021. Lecture Notes in Computer Science(), vol 12867. Springer, Cham. https://doi.org/10.1007/978-3-030-86593-1_3
Download citation
DOI: https://doi.org/10.1007/978-3-030-86593-1_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-86592-4
Online ISBN: 978-3-030-86593-1
eBook Packages: Computer ScienceComputer Science (R0)