Decidability of code properties

Henning Fernau; Klaus Reinhardt; Ludwig Staiger

RAIRO - Theoretical Informatics and Applications (2007)

  • Volume: 41, Issue: 3, page 243-259
  • ISSN: 0988-3754

Abstract

top
We explore the borderline between decidability and undecidability of the following question: “Let C be a class of codes. Given a machine 𝔐 of type X, is it decidable whether the language L ( 𝔐 ) lies in C 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.

How to cite

top

Fernau, Henning, Reinhardt, Klaus, and Staiger, Ludwig. "Decidability of code properties." RAIRO - Theoretical Informatics and Applications 41.3 (2007): 243-259. <http://eudml.org/doc/250070>.

@article{Fernau2007,
abstract = { We explore the borderline between decidability and undecidability of the following question: “Let C be a class of codes. Given a machine $\{\mathfrak\{M\}\}$ of type X, is it decidable whether the language $L(\{\{\mathfrak\{M\}\}\})$ lies in C 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. },
author = {Fernau, Henning, Reinhardt, Klaus, Staiger, Ludwig},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Partially blind counter machines; prefix code; infix code; bifix code; deciphering delay; decidability; partially blind counter machines; bifix code},
language = {eng},
month = {9},
number = {3},
pages = {243-259},
publisher = {EDP Sciences},
title = {Decidability of code properties},
url = {http://eudml.org/doc/250070},
volume = {41},
year = {2007},
}

TY - JOUR
AU - Fernau, Henning
AU - Reinhardt, Klaus
AU - Staiger, Ludwig
TI - Decidability of code properties
JO - RAIRO - Theoretical Informatics and Applications
DA - 2007/9//
PB - EDP Sciences
VL - 41
IS - 3
SP - 243
EP - 259
AB - We explore the borderline between decidability and undecidability of the following question: “Let C be a class of codes. Given a machine ${\mathfrak{M}}$ of type X, is it decidable whether the language $L({{\mathfrak{M}}})$ lies in C 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.
LA - eng
KW - Partially blind counter machines; prefix code; infix code; bifix code; deciphering delay; decidability; partially blind counter machines; bifix code
UR - http://eudml.org/doc/250070
ER -

References

top
  1. J. Berstel, Transductions and Context-Free Languages, LAMM38. Teubner, Stuttgart (1979).  
  2. J. Berstel and D. Perrin. Theory of Codes. Pure and Applied Mathematics, Academic Press, Orlando (1985).  
  3. J. Berstel and D. Perrin. Trends in the theory of codes. EATCS Bull.29 (1986) 84–95.  
  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 Cybernetica11 (1994) 241–256.  
  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.  
  7. H. Fernau and L. Staiger, IFS and control languages. Inform. Comput.168 (2001) 125–143.  
  8. S. Ginsburg, S. Greibach, and M. Harrison, One-way stack automata. J. Assoc. Comput. Machinery14 (1967) 389–418.  
  9. S. Greibach, Remarks on blind and partially blind one-way multicounter machines. Theoret. Comput. Sci.7 (1978) 311–324.  
  10. M.A. Harrison, Introduction to Formal Language Theory. Addison-Wesley series in computer science. Addison-Wesley, Reading (MA) (1978).  
  11. J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (MA)(1979).  
  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.  
  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.  
  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.  
  16. V.I. Levenshtejn, Some properties of coding and self-adjusting automata for decoding messages (in Russian). Problemy Kibernetiki11 (1964) 63–121. As regards translations, see [13], 604.  
  17. R. Lindner and L. Staiger, Algebraische Codierungstheorie; Theorie der sequentiellen Codierungen, 11 Elektronisches Rechnen und Regeln. Akademie-Verlag, Berlin (1977).  
  18. B.E. Litow, Parallel complexity of the regular code problem. Inform. Comput. 86 (1990) 107–114.  
  19. E. Mayr, An algorithm for the general Petri net reachability problem. SIAM J. Comput.13 (1984) 441–459.  
  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.  
  21. M.L. Minsky, Computation: Finite and Infinite Machines. Prentice-Hall (1971).  
  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. Sci386 (1988) 186–198.  
  24. W. Rytter, The space complexity of the unique decipherability problem. Inform. Process. Lett.23 (1986) 1–3.  
  25. L. Staiger, On infinitary finite length codes. RAIRO-Theor. Inf. Appl.20 (1986) 483–494.  
  26. L. Staiger, Codes, simplifying words, and open set condition. Inform. Process. Lett.58 (1996) 297–301.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.