Paper published in a book (Scientific congresses and symposiums)
Epsilon Automata on Linear Orderings
Boigelot, Bernard; Braipson, Thomas; Clara, Tom
2025 • In Castiglione, Giuseppa; Mantaci, Sabrina (Eds.) Implementation and Application of Automata - 29th International Conference, CIAA 2025, Proceedings
Epsilon transitions; Finite automata; Linear orderings
Abstract :
[en] Automata on linear orderings are a form of finite-state automata introduced by Bruyère and Carton, that generalize the concepts of finite-word, infinite-word, and transfinite-word automata. They recognize words indexed by linear orderings, defined as mappings from the elements of such orderings to a finite alphabet. Some theoretical developments involving automata on linear orderings are hindered by the fact that their definition does not allow epsilon transitions, i.e., transitions with an empty label. In this paper, we define a variant of automata on linear orderings that allows such transitions in their transition relation, and show that this extension does not modify the expressive power of the automata. We motivate the usefulness of epsilon automata on linear orderings by using them for correcting an erroneous construction in the original proof of equivalence between automata on linear orderings and the corresponding notion of regular expressions.
Disciplines :
Computer science
Author, co-author :
Boigelot, Bernard ; Université de Liège - ULiège > Département d'électricité, électronique et informatique (Institut Montefiore) > Informatique
Braipson, Thomas ; Université de Liège - ULiège > Département d'électricité, électronique et informatique (Institut Montefiore) > Informatique
Clara, Tom ; Université de Liège - ULiège > Département d'électricité, électronique et informatique (Institut Montefiore) > Informatique
Language :
English
Title :
Epsilon Automata on Linear Orderings
Publication date :
2025
Event name :
29th International Conference, CIAA 2025
Event place :
Palermo, Italy
Event date :
22-09-2025 => 25-09-2025
Audience :
International
Main work title :
Implementation and Application of Automata - 29th International Conference, CIAA 2025, Proceedings
Bès, A., Carton, O.: A Kleene theorem for languages of words indexed by linear orderings. Int. J. Found. Comput. Sci. 17(03), 519–541 (2006)
Boigelot, B., Fontaine, P., Vergain, B.: Non-emptiness test for automata over words indexed by the reals and rationals. In: Fazekas, S.Z. (ed.) CIAA 2024. LNCS, vol. 15015, pp. 94–108. Springer, Cham (2024). https://doi.org/10.1007/978-3-031-71112-1 7
Bruyère, V., Hansel, G., Michaux, C., Villemaire, R.: Logic and p-recognizable sets of integers. Bull. Belgian Math. Soc. 1(2), 191–238 (1994)
Bruyère, V., Carton, O.: Automata on linear orderings. J. Comput. Syst. Sci. 73(1), 1–24 (2007)
Büchi, J.R.: On a decision method in restricted second order arithmetic. In: Proceedings of the International Congress on Logic, Methodology and Philosophy of Science, pp. 1–12. Stanford University Press, Stanford (1962)
Choueka, Y.: Finite automata, definable sets, and regular expressions over ωn-tapes. J. Comput. Syst. Sci. 17(1), 81–97 (1978)
Cristau, J.: Automata and temporal logic over arbitrary linear time. In: Proceedings of the IARCS 29th Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). LIPIcs, vol. 4, pp. 133–144 (2009)
Nivat, M., Perrin, D.: Ensembles reconnaissables de mots biinfinis. In: Proceedings of the 14th Annual ACM Symposium on Theory of Computing (STOC), pp. 47–59. ACM (1982)
Rabinovich, A.: Temporal logics over linear time domains are in PSPACE. Inf. Comput. 210, 40–67 (2012)
Rispal, C., Carton, O.: Complementation of rational sets on countable scattered linear orderings. Int. J. Found. Comput. Sci. 16(04), 767–786 (2005)
Rosenstein, J.G.: Linear Orderings. Academic Press (1982)
Wojciechowski, J.: Finite automata on transfinite sequences and regular expressions. Fund. Inform. 8(3–4), 379–396 (1985)
