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
Access Full Article
top
Abstract
topHow to cite
topFernau, 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- J. Berstel, Transductions and Context-Free Languages, LAMM38. 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).
- J. Devolder, M. Latteux, I. Litovski and L. Staiger, Codes and infinite words. Acta Cybernetica11 (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.
- H. Fernau and L. Staiger, IFS and control languages. Inform. Comput.168 (2001) 125–143.
- S. Ginsburg, S. Greibach, and M. Harrison, One-way stack automata. J. Assoc. Comput. Machinery14 (1967) 389–418.
- S. Greibach, Remarks on blind and partially blind one-way multicounter machines. Theoret. Comput. Sci.7 (1978) 311–324.
- 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).
- H. Jürgensen, K. Salomaa and S. Yu, Transducers and the decidability of independence in free monoids. Theoret. Comput. Sci.134 (1994) 107–117.
- 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.
- 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.
- 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.
- E. Mayr, An algorithm for the general Petri net reachability problem. SIAM J. Comput.13 (1984) 441–459.
- 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.
- 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).
- 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.
- W. Rytter, The space complexity of the unique decipherability problem. Inform. Process. Lett.23 (1986) 1–3.
- L. Staiger, On infinitary finite length codes. RAIRO-Theor. Inf. Appl.20 (1986) 483–494.
- L. Staiger, Codes, simplifying words, and open set condition. Inform. Process. Lett.58 (1996) 297–301.
NotesEmbed ?
topYou 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.