Decidability of code properties
Fernau, Henning ; Reinhardt, Klaus ; Staiger, Ludwig
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007), p. 243-259 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

We explore the borderline between decidability and undecidability of the following question: “Let 𝒞 be a class of codes. Given a machine 𝔐 of type X, is it decidable whether the language L(𝔐) lies in 𝒞 or not?” for codes in general, ω-codes, codes of finite and bounded deciphering delay, prefix, suffix and bi(pre)fix codes, and for finite automata equipped with different versions of push-down stores and counters.

Publié le : 2007-01-01
DOI : https://doi.org/10.1051/ita:2007019
Classification:  68Q45,  03D05,  94A45,  94B99 
@article{ITA_2007__41_3_243_0,
     author = {Fernau, Henning and Reinhardt, Klaus and Staiger, Ludwig},
     title = {Decidability of code properties},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {41},
     year = {2007},
     pages = {243-259},
     doi = {10.1051/ita:2007019},
     mrnumber = {2354356},
     zbl = {pre05211858},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2007__41_3_243_0}
}

Fernau, Henning; Reinhardt, Klaus; Staiger, Ludwig. Decidability of code properties. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007) pp. 243-259. doi : 10.1051/ita:2007019. http://gdmltest.u-ga.fr/item/ITA_2007__41_3_243_0/

[1] J. Berstel, Transductions and Context-Free Languages, LAMM 38. Teubner, Stuttgart (1979). | Zbl 0424.68040

[2] J. Berstel and D. Perrin. Theory of Codes. Pure and Applied Mathematics, Academic Press, Orlando (1985). | Zbl 0587.68066

[3] J. Berstel and D. Perrin. Trends in the theory of codes. EATCS Bull. 29 (1986) 84-95. | Zbl 1022.94506

[4] V. Bruyère. Automata and codes with bounded deciphering delay, in Proc. LATIN'92, edited by I. Simon. Lect. Notes Comput. Sci. 583 (1992).

[5] J. Devolder, M. Latteux, I. Litovski and L. Staiger, Codes and infinite words. Acta Cybernetica 11 (1994) 241-256. | Zbl 0938.68691

[6] H. Fernau, IiFS and codes. In Developments in Theoretical Computer Science, edited by J. Dassow and A. Kelemenová. Gordon and Breach Science Publishers, Basel (1994) 141-152. | Zbl 0963.68093

[7] H. Fernau and L. Staiger, IFS and control languages. Inform. Comput. 168 (2001) 125-143. | Zbl 1007.68096

[8] S. Ginsburg, S. Greibach, and M. Harrison, One-way stack automata. J. Assoc. Comput. Machinery 14 (1967) 389-418. | Zbl 0171.14803

[9] S. Greibach, Remarks on blind and partially blind one-way multicounter machines. Theoret. Comput. Sci. 7 (1978) 311-324. | Zbl 0389.68030

[10] M.A. Harrison, Introduction to Formal Language Theory. Addison-Wesley series in computer science. Addison-Wesley, Reading (MA) (1978). | MR 526397 | Zbl 0411.68058

[11] J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (MA)(1979). | MR 645539 | Zbl 0426.68001

[12] H. Jürgensen, K. Salomaa and S. Yu, Transducers and the decidability of independence in free monoids. Theoret. Comput. Sci. 134 (1994) 107-117. | Zbl 0938.68710

[13] H. Jürgensen and S. Konstantinidis, Codes. in Handbook of Formal Languages, Volume I, edited by G. Rozenberg and A. Salomaa. Springer, Berlin (1997) 511-607. | Zbl 0866.68057

[14] S.R. Kosaraju, Decidability of reachability in vector addition systems, in Proceedings 14th Annual ACM STOC (1984) 267-281.

[15] K.-J. Lange and K. Reinhardt, Set automata. in Combinatorics, Complexity and Logic, Proceedings of the DMTCS'96, edited by D.S. Bridges. Springer, Berlin (1996) 321-329. | Zbl 0914.68117

[16] V.I. Levenshtejn, Some properties of coding and self-adjusting automata for decoding messages (in Russian). Problemy Kibernetiki 11 (1964) 63-121. As regards translations, see [13], 604. | Zbl 0235.94002

[17] R. Lindner and L. Staiger, Algebraische Codierungstheorie; Theorie der sequentiellen Codierungen, 11 Elektronisches Rechnen und Regeln. Akademie-Verlag, Berlin (1977). | MR 469495 | Zbl 0363.94016

[18] B.E. Litow, Parallel complexity of the regular code problem. Inform. Comput. 86 (1990) 107-114. | Zbl 0699.68071

[19] E. Mayr, An algorithm for the general Petri net reachability problem. SIAM J. Comput. 13 (1984) 441-459. | Zbl 0563.68057

[20] M.L. Minsky, Recursive unsolvability of Post's problem of “tag” and other topics in theory of Turing machines. Ann. Math. 74 (1961) 437-455. | Zbl 0105.00802

[21] M.L. Minsky, Computation: Finite and Infinite Machines. Prentice-Hall (1971). | MR 356580 | Zbl 0195.02402

[22] K. Reinhardt, Prioritätszählerautomaten und die Synchronisation von Halbspursprachen. Dissertation, Institut für Informatik, Universität Stuttgart (1994).

[23] A. Restivo, Codes and automata, in Formal Properties of Finite Automata and Applications, edited by J.E. Pin. Lect. Notes Comput. Sci 386 (1988) 186-198.

[24] W. Rytter, The space complexity of the unique decipherability problem. Inform. Process. Lett. 23 (1986) 1-3. | Zbl 0609.68037

[25] L. Staiger, On infinitary finite length codes. RAIRO-Theor. Inf. Appl. 20 (1986) 483-494. | Numdam | Zbl 0628.68056

[26] L. Staiger, Codes, simplifying words, and open set condition. Inform. Process. Lett. 58 (1996) 297-301. | Zbl 1004.68528