Decidability of code properties
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007) no. 3, pp. 243-259.

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.

DOI : 10.1051/ita:2007019
Classification : 68Q45, 03D05, 94A45, 94B99
Mots-clés : partially blind counter machines, prefix code, infix code, bifix code, deciphering delay, decidability 
@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},
     pages = {243--259},
     publisher = {EDP-Sciences},
     volume = {41},
     number = {3},
     year = {2007},
     doi = {10.1051/ita:2007019},
     mrnumber = {2354356},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita:2007019/}
}
TY  - JOUR
AU  - Fernau, Henning
AU  - Reinhardt, Klaus
AU  - Staiger, Ludwig
TI  - Decidability of code properties
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2007
SP  - 243
EP  - 259
VL  - 41
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2007019/
DO  - 10.1051/ita:2007019
LA  - en
ID  - ITA_2007__41_3_243_0
ER  - 
%0 Journal Article
%A Fernau, Henning
%A Reinhardt, Klaus
%A Staiger, Ludwig
%T Decidability of code properties
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2007
%P 243-259
%V 41
%N 3
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita:2007019/
%R 10.1051/ita:2007019
%G en
%F 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) no. 3, pp. 243-259. doi : 10.1051/ita:2007019. http://www.numdam.org/articles/10.1051/ita:2007019/

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

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

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

[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

[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

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

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

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

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

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

[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

[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

[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

[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

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

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

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

[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

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

[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

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

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

Cité par Sources :