Decidability of code properties

DOI10.1051/ita:2007019zbMath1203.68084OpenAlexW2150836653MaRDI QIDQ5425746

Ludwig Staiger, Klaus Reinhardt, Henning Fernau

Publication date: 14 November 2007

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_2007__41_3_243_0

zbMATH Keywords

decidabilitydeciphering delayprefix codebifix codeinfix codepartially blind counter machines

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Theory of error-correcting codes and error-detecting codes (94B99) Prefix, length-variable, comma-free codes (94A45)

Related Items

FORMAL DESCRIPTIONS OF CODE PROPERTIES: DECIDABILITY, COMPLEXITY, IMPLEMENTATION ⋮ Automata for solid codes ⋮ Picture codes and deciphering delay ⋮ DIRECTED FIGURE CODES: DECIDABILITY FRONTIER

Cites Work

• Codes, simplifying words, and open set condition
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Parallel complexity of the regular code problem
• The space complexity of the unique decipherability problem
• Maximal codes with bounded deciphering delay
• Remarks on blind and partially blind one-way multicounter machines
• Transducers and the decidability of independence in free monoids
• Iterated function systems and control languages
• An Algorithm for the General Petri Net Reachability Problem
• On infinitary finite length codes
• One-way stack automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item