Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-18T09:08:33.300Z Has data issue: false hasContentIssue false
  • English
  • Français

Decidability of code properties

Published online by Cambridge University Press:  25 September 2007

Henning Fernau ,
Klaus Reinhardt  and
Ludwig Staiger
Henning Fernau
Affiliation:
Fachbereich IV, Abteilung Informatik, Universität Trier, 54286 Trier, Germany; [email protected]
Klaus Reinhardt
Affiliation:
Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, Sand 13, 72076 Tübingen, Germany; [email protected]
Ludwig Staiger
Affiliation:
Institut für Informatik, Martin-Luther-Universität Halle-Wittenberg, von-Seckendorff-Platz 1, 06099 Halle, Germany; [email protected]
Get access

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.

Keywords

Partially blind counter machinesprefix codeinfix codebifix codedeciphering delaydecidability
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 41 , Issue 3 , July 2007 , pp. 243 - 259
Copyright
© EDP Sciences, 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

J. Berstel, Transductions and Context-Free Languages, LAMM 38. Teubner, Stuttgart (1979).
J. Berstel and D. Perrin. Theory of Codes. Pure and Applied Mathematics, Academic Press, Orlando (1985).
J. Berstel and D. Perrin. Trends in the theory of codes. EATCS Bull. 29 (1986) 84–95.
V. Bruyère. Automata and codes with bounded deciphering delay, in Proc. LATIN'92, edited by I. Simon. Lect. Notes Comput. Sci. 583 (1992).
Devolder, J., Latteux, M., Litovski, I. and Staiger, L., Codes and infinite words. Acta Cybernetica 11 (1994) 241–256.
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.
Fernau, H. and Staiger, L., IFS and control languages. Inform. Comput. 168 (2001) 125–143. CrossRef
Ginsburg, S., Greibach, S., and Harrison, M., One-way stack automata. J. Assoc. Comput. Machinery 14 (1967) 389–418. CrossRef
Greibach, S., Remarks on blind and partially blind one-way multicounter machines. Theoret. Comput. Sci. 7 (1978) 311–324. CrossRef
M.A. Harrison, Introduction to Formal Language Theory. Addison-Wesley series in computer science. Addison-Wesley, Reading (MA) (1978).
J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (MA)(1979).
Jürgensen, H., Salomaa, K. and Transducers, S. Yu and the decidability of independence in free monoids. Theoret. Comput. Sci. 134 (1994) 107–117. CrossRef
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.
S.R. Kosaraju, Decidability of reachability in vector addition systems, in Proceedings 14th Annual ACM STOC (1984) 267–281.
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.
Levenshtejn, V.I., 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.
R. Lindner and L. Staiger, Algebraische Codierungstheorie; Theorie der sequentiellen Codierungen, 11 Elektronisches Rechnen und Regeln. Akademie-Verlag, Berlin (1977).
B.E. Litow, Parallel complexity of the regular code problem. Inform. Comput. 86 (1990) 107–114.
Mayr, E., An algorithm for the general Petri net reachability problem. SIAM J. Comput. 13 (1984) 441–459. CrossRef
Minsky, M.L., Recursive unsolvability of Post's problem of “tag” and other topics in theory of Turing machines. Ann. Math. 74 (1961) 437–455. CrossRef
M.L. Minsky, Computation: Finite and Infinite Machines. Prentice-Hall (1971).
K. Reinhardt, Prioritätszählerautomaten und die Synchronisation von Halbspursprachen. Dissertation, Institut für Informatik, Universität Stuttgart (1994).
Restivo, A., Codes and automata, in Formal Properties of Finite Automata and Applications, edited by J.E. Pin. Lect. Notes Comput. Sci 386 (1988) 186–198. CrossRef
Rytter, W., The space complexity of the unique decipherability problem. Inform. Process. Lett. 23 (1986) 1–3. CrossRef
Staiger, L., On infinitary finite length codes. RAIRO-Theor. Inf. Appl. 20 (1986) 483–494. CrossRef
Staiger, L., Codes, simplifying words, and open set condition. Inform. Process. Lett. 58 (1996) 297–301. CrossRef