Geodesic
On infinite real trace rational languages of maximum topological complexity
Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part IX, Tome 316 (2004), pp. 205-223 
O. Finkel; J.-P. Ressayre; P. Simonnet. On infinite real trace rational languages of maximum topological complexity. Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part IX, Tome 316 (2004), pp. 205-223. http://geodesic.mathdoc.fr/item/ZNSL_2004_316_a10/
@article{ZNSL_2004_316_a10,
     author = {O. Finkel and J.-P. Ressayre and P. Simonnet},
     title = {On infinite real trace rational languages of maximum topological complexity},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {205--223},
     year = {2004},
     volume = {316},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2004_316_a10/}
}
TY  - JOUR
AU  - O. Finkel
AU  - J.-P. Ressayre
AU  - P. Simonnet
TI  - On infinite real trace rational languages of maximum topological complexity
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2004
SP  - 205
EP  - 223
VL  - 316
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2004_316_a10/
LA  - en
ID  - ZNSL_2004_316_a10
ER  - 
%0 Journal Article
%A O. Finkel
%A J.-P. Ressayre
%A P. Simonnet
%T On infinite real trace rational languages of maximum topological complexity
%J Zapiski Nauchnykh Seminarov POMI
%D 2004
%P 205-223
%V 316
%U http://geodesic.mathdoc.fr/item/ZNSL_2004_316_a10/
%G en
%F ZNSL_2004_316_a10

Voir la notice du chapitre de livre provenant de la source Math-Net.Ru

We consider the set $\mathbb R^{\omega}(\Gamma,D)$ of infinite real traces, over a dependence alphabet $(\Gamma,D)$ with no isolated letter, equipped with the topology induced by the prefix metric. We then prove that all rational languages of infinite real traces are analytic sets. We reprove also that there exist some rational languages of infinite real traces which are analytic but non Borel sets, and even ${\boldsymbol{\Sigma}}^1_1$-complete, hence of maximum possible topological complexity. For that purpose we give an example of $\boldsymbol{\Sigma}^1_1$-complete language which is fundamentally different from the known example of $\boldsymbol{\Sigma}^1_1$-complete infinitary rational relation given in [10].

[1] X. Augros, Des Algorithmes Autour des Codes Rationnels, Ph.D. Thesis, Université de Nice-Sopia Antipolis, December, 2001 | Zbl

[2] M. K. Ahmad, X. Augros, “Some Results on Codes for Generalized Factorizations”, J. of Automata, Languages and Combinatorics, 6:3 (2001), 239–251 | MR | Zbl

[3] J-H. Altenbernd, W. Thomas, S. Wöhrle, “Tiling Systems over Infinite Pictures and their Acceptance Conditions”, Proceedings of the 6th International Conference on Developements in Language Theory, DLT 2002, Lecture Notes in Computer Science, 2450, Springer, 2003, 297–306 | MR | Zbl

[4] P. Bonnizzoni, G. Mauri, G. Pighizzini, Proceedings of the ASMICS Workshop Free Partially Commutative Monoids, Kochel am See, October 1989, Report TUM-I9002, TU München, 1990, 1–10

[5] P. Cartier, D. Foata, Problèmes Combinatoires de Commutation et de Réarrangements, Lecture Notes in Mathematics, 85, Springer-Verlag, Berlin-Heidelberg-New York, 1969 | MR

[6] V. Diekert, G. Rozenberg (ed.), The Book of Traces, World Scientific, Singapore, 1995 | MR

[7] O. Finkel, “Topological Properties of Omega Context Free Languages”, Theoretical Computer Science, 262:1–2 (2001), 669–697 | DOI | MR | Zbl

[8] O. Finkel, “Borel Hierarchy and Omega Context Free Languages”, Theoretical Computer Science, 290:3 (2003), 1385–1405 | DOI | MR | Zbl

[9] O. Finkel, “Ambiguity in Omega Context Free Languages”, Theoretical Computer Science, 301:1–3 (2003), 217–270 | DOI | MR | Zbl

[10] O. Finkel, “On the Topological Complexity of Infinitary Rational Relations”, RAIRO-Theoretical Informatics and Applications, 37:2 (2003), 105–113 | DOI | MR | Zbl

[11] O. Finkel, “Undecidability of Topological and Arithmetical Properties of Infinitary Rational Relations”, RAIRO-Theoretical Informatics and Applications, 37:2 (2003), 115–126 | DOI | MR | Zbl

[12] O. Finkel, P. Simonnet, “Topology and Ambiguity in Omega Context Free Languages”, Bulletin of the Belgian Mathematical Society, 10:5 (2003), 707–722 | MR | Zbl

[13] O. Finkel, “On Recognizable Languages of Infinite Pictures”, International Journal of Foundations of Computer Science (to appear)

[14] O. Finkel, “An $\omega$-Power of a Finitary Language Which is a Borel Set of Infinite Rank”, Fundamenta Informaticae, 62:3–4 (2004), 333–342 | MR | Zbl

[15] P. Gastin, “Recognizable and Rational Languages of Finite and Infinite Traces”, Actes du STACS'91, Lecture Notes in Computer Science, 480, 1991, 89–104 | DOI | MR | Zbl

[16] P. Gastin, A. Petit, “Infinite Traces”, Chapter in The Book of Traces, ed. V. Diekert, G. Rozenberg, World Scientific, 1995, 393–486 | MR

[17] P. Gastin, A. Petit, W. Zielonka, “An Extension of Kleene's and Ochmanski's Theorems to Infinite Traces”, Fundamental Study, Theoretical Computer Science, 125 (1994), 167–204 | MR | Zbl

[18] H. J. Hoogeboom, A. Muscholl, “The Code Problem for Traces - Improving the Boundaries”, Theoretical Computer Science, 172 (1997), 309–321 | DOI | MR | Zbl

[19] A. S. Kechris, Classical Descriptive Set Theory, Springer-Verlag, 1995 | MR

[20] R. Kummetz, D. Kuske, “The Topology of Mazurkiewicz Traces”, Theoretical Computer Science, 305:1–3 (2003), 237–258 | DOI | MR | Zbl

[21] M. Kwiatkowska, “A Metric for Traces”, Information Processing Letters, 35 (1990), 129–135 | DOI | MR | Zbl

[22] L. H. Landweber, “Decision Problems for $\omega$-Automata”, Math. Syst. Theory, 3:4 (1969), 376–384 | DOI | MR | Zbl

[23] D. Lecomte, Sur les Ensembles de Phrases Infinies Constructibles a Partir d'un Dictionnaire sur un Alphabet Fini, Séminaire d'Initiation a l'Analyse, v. 1, 2001–2002

[24] H. Lescow, W. Thomas, “Logical Specifications of Infinite Computations”, A Decade of Concurrency, LNCS, 803, eds. J. W. de Bakker et al., Springer, 1994, 583–621 | MR

[25] A. Mazurkiewicz, Concurrent Programs Schemes and their Interpretation, DAIMI Report PB-78, Aarhus University, Aarhus, 1977 | MR

[26] Y. N. Moschovakis, Descriptive Set Theory, North-Holland, Amsterdam, 1980 | MR | Zbl

[27] D. Niwinski, An example of Non Borel Set of Infinite Trees Recognizable by a Rabin Automaton, Polish, Manuscript, University of Warsaw, 1985

[28] D. Niwinski, Problem on $\omega$-Powers posed in the Proceedings of the 1990 Workshop “Logics and Recognizable Sets”, Univ. Kiel

[29] D. Perrin, J.-E. Pin, Infinite Words, Automata, Semigroups, Logic and Games, Pure and Applied Mathematics, 141, Elsevier, 2004 | Zbl

[30] P. Simonnet, Automates et Théorie Descriptive, Ph. D. Thesis, Université Paris 7, March, 1992

[31] P. Simonnet, “Automate d' Arbres Infinis et Choix Borélien”, C.R.A.S. Paris, 316:1 (1993), 97–100 | MR | Zbl

[32] L. Staiger, “Hierarchies of Recursive $\omega$-Languages”, J. Inform. Process. Cybernetics EIK, 22:5–6 (1986), 219–241 | MR | Zbl

[33] L. Staiger, $\omega$-Languages, Chapter of the Handbook of Formal languages, v. 3, eds. G. Rozenberg, A. Salomaa, Springer-Verlag, Berlin | MR

[34] L. Staiger, “On $\omega$-Power Languages”, New Trends in Formal Languages, Control, Cooperation, and Combinatorics, Lecture Notes in Computer Science, 1218, Springer-Verlag, Berlin, 1997, 377–393 | MR

[35] W. Thomas, “Automata on Infinite Objects”, Handbook of Theoretical Computer Science, Vol. B, ed. J. Van Leeuwen, Elsevier, Amsterdam, 1990, 133–191 | MR | Zbl