Some complete \(\omega\)-powers of a one-counter language, for any Borel class of finite rank. (English) Zbl 1498.03104
Summary: We prove that, for any natural number \(n\ge 1\), we can find a finite alphabet \(\Sigma\) and a finitary language \(L\) over \(\Sigma\) accepted by a one-counter automaton, such that the \(\omega \)-power
\[ \begin{aligned} L^\infty :=\{ w_0w_1\ldots \in \Sigma^\omega \mid \forall i\in \omega w_i\in L\} \end{aligned} \]
is \(\boldsymbol{\Pi }^0_n\)-complete. We prove a similar result for the class \({\boldsymbol{\Sigma }}^0_n\).
\[ \begin{aligned} L^\infty :=\{ w_0w_1\ldots \in \Sigma^\omega \mid \forall i\in \omega w_i\in L\} \end{aligned} \]
is \(\boldsymbol{\Pi }^0_n\)-complete. We prove a similar result for the class \({\boldsymbol{\Sigma }}^0_n\).
MSC:
| 03E15 | Descriptive set theory |
| 54H05 | Descriptive set theory (topological aspects of Borel, analytic, projective, etc. sets) |
| 03D05 | Automata and formal grammars in connection with logical questions |
| 68Q45 | Formal languages and automata |
References:
| [1] | Autebert, J.-M., Berstel, J., Boasson, L.: Context free languages and pushdown automata. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 1. Springer (1996) · Zbl 0843.68050 |
| [2] | Cohen, RS; Gold, AY, Theory of \(\omega \)-languages, parts one and two, J. Comput. Syst. Sci., 15, 169-208 (1977) · Zbl 0363.68113 · doi:10.1016/S0022-0000(77)80004-4 |
| [3] | Duparc, J., Finkel, O.: An \(\omega \)-power of a context free language which is Borel above \({\Delta }_\omega^0\). In: Proceedings of the International Conference Foundations of the Formal Sciences V: Infinite Games, November 26th to 29th, 2004, Bonn, Germany, volume 11 of College Publications at King’s College (Studies in Logic), pp. 109-122. London (2007) · Zbl 1213.03057 |
| [4] | Duparc, J., Wadge hierarchy and Veblen hierarchy: part 1: Borel sets of finite rank, J. Symb. Log., 66, 1, 56-86 (2001) · Zbl 0979.03039 · doi:10.2307/2694911 |
| [5] | Finkel, O., Topological properties of omega context free languages, Theor. Comput. Sci., 262, 1-2, 669-697 (2001) · Zbl 0992.68125 · doi:10.1016/S0304-3975(00)00405-9 |
| [6] | Finkel, O., Borel hierarchy and omega context free languages, Theor. Comput. Sci., 290, 3, 1385-1405 (2003) · Zbl 1051.68094 · doi:10.1016/S0304-3975(02)00042-7 |
| [7] | Finkel, O., An omega-power of a finitary language which is a Borel set of infinite rank, Fundam. Inf., 62, 3-4, 333-342 (2004) · Zbl 1102.03041 |
| [8] | Finkel, O., Borel ranks and Wadge degrees of omega context free languages, Math. Struct. Comput. Sci., 16, 5, 813-840 (2006) · Zbl 1121.03047 · doi:10.1017/S0960129506005597 |
| [9] | Finkel, O., Lecomte, D.: There exist some \(\omega \)-powers of any Borel rank. In: Proceedings of the 16th EACSL Annual International Conference on Computer Science and Logic, CSL 2007, Lausanne, Switzerland, September 11-15, 2007, volume 4646 of Lecture Notes in Computer Science, pp. 115-129. Springer (2007) · Zbl 1179.68069 |
| [10] | Finkel, O.; Lecomte, D., Classical and effective descriptive complexities of omega-powers, Ann. Pure Appl. Log., 160, 2, 163-191 (2009) · Zbl 1170.03025 · doi:10.1016/j.apal.2009.02.005 |
| [11] | Hopcroft, JE; Motwani, R.; Ullman, JD, Introduction to Automata Theory, Languages, and Computation (2001), Reading: Addison-Wesley Publishing Co., Reading · Zbl 0980.68066 |
| [12] | Kechris, AS, Classical Descriptive Set Theory (1995), New York: Springer, New York · Zbl 0819.04002 · doi:10.1007/978-1-4612-4190-4 |
| [13] | Lecomte, D., Omega-powers and descriptive set theory, J. Symb. Log., 70, 4, 1210-1232 (2005) · Zbl 1117.03055 · doi:10.2178/jsl/1129642123 |
| [14] | Moschovakis, YN, Descriptive Set Theory (1980), Amsterdam: North-Holland Publishing Co., Amsterdam · Zbl 0433.03025 |
| [15] | Niwinski, D.: A problem on \(\omega \)-powers. In: 1990 Workshop on Logics and Recognizable Sets. University of Kiel (1990) |
| [16] | Perrin, D.; Pin, J-E, Infinite Words, Automata, Semigroups, Logic and Games, volume 141 of Pure and Applied Mathematics (2004), Amsterdam: Elsevier, Amsterdam · Zbl 1094.68052 |
| [17] | Simonnet, P.: Automates et théorie descriptive. Ph.D. thesis, Université Paris VII (1992) |
| [18] | Staiger, L., Hierarchies of recursive \(\omega \)-languages, Elektronische Informationsverarbeitung und Kybernetik, 22, 5-6, 219-241 (1986) · Zbl 0627.03024 |
| [19] | Staiger, L.: \( \omega \)-languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 3, pp. 339-387. Springer, Berlin (1997) |
| [20] | Thomas, W.; van Leeuwen, J., Automata on infinite objects, Handbook of Theoretical Computer Science, volume B, Formal Models and Semantics, 135-191 (1990), Amsterdam: Elsevier, Amsterdam · Zbl 0714.68001 |
| [21] | Wadge, W.: Reducibility and determinateness in the Baire space. Ph.D. thesis, University of California, Berkeley (1983) |
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.
