Automata on linear orderings. (English) Zbl 1178.68307
Summary: We consider words indexed by linear orderings. These extend finite, (bi-)infinite words and words on ordinals. We introduce finite automata and rational expressions for these words. We prove that for countable scattered linear orderings, these two notions are equivalent. This result extends Kleene’s theorem.
MSC:
| 68Q45 | Formal languages and automata |
References:
| [1] | E. Asarin, P. Caspi, O. Maler, A Kleene theorem for timed automata, in: Proceedings, Twelfth Annual IEEE Symposium on Logic in Computer Science, 1997, pp. 160-171; E. Asarin, P. Caspi, O. Maler, A Kleene theorem for timed automata, in: Proceedings, Twelfth Annual IEEE Symposium on Logic in Computer Science, 1997, pp. 160-171 |
| [2] | Bedon, N.; Carton, O., An Eilenberg theorem for words on countable ordinals, (Lucchesi, C. L.; Moura, A. V., Latin ’98: Theoretical Informatics. Latin ’98: Theoretical Informatics, Lecture Notes in Comput. Sci., vol. 1380 (1998), Springer-Verlag), 53-64 · Zbl 0906.20045 |
| [3] | Bérard, B.; Picaronny, C., Accepting Zeno words without making time stand still, (Mathematical Foundations of Computer Science 1997. Mathematical Foundations of Computer Science 1997, Lecture Notes in Comput. Sci., vol. 1295 (1997)), 149-158 · Zbl 0941.68044 |
| [4] | Bès, A.; Carton, O., A Kleene theorem for languages of words indexed by linear orderings, (De Felice, C.; Restivo, A., DLT 2005. DLT 2005, Lecture Notes in Comput. Sci., vol. 3572 (2005), Springer-Verlag), 158-167 · Zbl 1132.68438 |
| [5] | Bruyère, V.; Carton, O., Automata on linear orderings, (Sgall, J.; Pultr, A.; Kolman, P., MFCS 2001. MFCS 2001, Lecture Notes in Comput. Sci., vol. 2136 (2001)), 236-247 · Zbl 0999.68100 |
| [6] | Bruyère, V.; Carton, O.; Sénizergues, G., Tree automata and automata on linear orderings, (Harju, T.; Karhumäki, J., WORDS 2003. WORDS 2003, TUCS Gen. Publ., vol. 27 (2003), Turku Center for Computer Science), 222-231 · Zbl 1040.68072 |
| [7] | Büchi, J. R., Weak second-order arithmetic and finite automata, Z. Math. Logik Grundl. Math., 6, 66-92 (1960) · Zbl 0103.24705 |
| [8] | Büchi, J. R., On a decision method in the restricted second-order arithmetic, (Proc. Int. Congress Logic, Methodology, and Philosophy of Science. Proc. Int. Congress Logic, Methodology, and Philosophy of Science, Berkeley, 1960 (1962), Stanford Univ. Press), 1-11 · Zbl 0215.32401 |
| [9] | Büchi, J. R., Transfinite automata recursions and weak second order theory of ordinals, (Proc. Int. Congress Logic, Methodology, and Philosophy of Science. Proc. Int. Congress Logic, Methodology, and Philosophy of Science, Jerusalem, 1964 (1965), North-Holland), 2-23 · Zbl 0207.31001 |
| [10] | Carton, O., Accessibility in automata on scattered linear orderings, (Diks, K.; Rytter, W., MFCS 2002. MFCS 2002, Lecture Notes in Comput. Sci., vol. 2420 (2002)), 155-164 · Zbl 1014.68081 |
| [11] | Choueka, Y., Finite automata, definable sets, and regular expressions over \(\omega^n\)-tapes, J. Comput. System Sci., 17, 1, 81-97 (1978) · Zbl 0386.03018 |
| [12] | Courcelle, B., Frontiers of infinite trees, RAIRO Theor. Inform., 12, 4, 319-337 (1978) · Zbl 0411.68065 |
| [13] | Girault-Beauquier, D., Bilimites de langages reconnaissables, Theoret. Comput. Sci., 33, 2-3, 335-342 (1984) · Zbl 0555.68044 |
| [14] | Hansen, M. R.; Pandya, P. K.; Chaochen, Z., Finite divergence, Theoret. Comput. Sci., 138, 1, 113-139 (1995) · Zbl 0874.68269 |
| [15] | Heilbrunner, S., An algorithm for the solution of fixed-point equations for infinite words, RAIRO Theor. Inform., 14, 2, 131-141 (1980) · Zbl 0433.68062 |
| [16] | Kleene, S. C., Representation of events in nerve nets and finite automata, (Shannon, C. E., Automata Studies (1956), Princeton Univ. Press: Princeton Univ. Press Princeton), 3-41 · Zbl 0061.01003 |
| [17] | M. Nivat, D. Perrin, Ensembles reconnaissables de mots bi-infinis, in: Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, 1982, pp. 47-59; M. Nivat, D. Perrin, Ensembles reconnaissables de mots bi-infinis, in: Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, 1982, pp. 47-59 |
| [18] | Perrin, D., Finite automata, (van Leeuwen, J., Handbook of Theoretical Computer Science, vol. B (1990), Elsevier), 1-57, (Chapter 1) · Zbl 0900.68312 |
| [19] | Perrin, D.; Pin, J.-É., Infinite Words (2004), Elsevier · Zbl 1094.68052 |
| [20] | Rispal, C.; Carton, O., Complementation of rational sets on countable scattered linear orderings, J. Found. Comput. Sci., 16, 4, 767-786 (2005) · Zbl 1161.68551 |
| [21] | Rosenstein, J. G., Linear Orderings (1982), Academic Press: Academic Press New York · Zbl 0179.01303 |
| [22] | Shelah, S., The monadic theory of order, Ann. of Math., 102, 379-419 (1975) · Zbl 0345.02034 |
| [23] | Thomas, W., On frontiers of regular sets, RAIRO Theor. Inform., 20, 371-381 (1986) · Zbl 0639.68071 |
| [24] | Thomas, W., Automata on infinite objects, (van Leeuwen, J., Handbook of Theoretical Computer Science, vol. B (1990), Elsevier), 133-191, (Chapter 4) · Zbl 0900.68316 |
| [25] | Wojciechowski, J., Finite automata on transfinite sequences and regular expressions, Fund. Inform., 8, 3-4, 379-396 (1985) · Zbl 0573.68045 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
