FORMAL DESCRIPTIONS OF CODE PROPERTIES: DECIDABILITY, COMPLEXITY, IMPLEMENTATION

DOI10.1142/S0129054112400059zbMath1279.68149MaRDI QIDQ2909182

Stavros Konstantinidis, Krystian Dudzinski

Publication date: 30 August 2012

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

complexitypropertiesautomatamaximalitydecidabilityimplementationcodeslanguagestransducersdescriptions

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (7)

On the maximality of languages with combined types of code properties ⋮ Approximate NFA universality and related problems motivated by information theory ⋮ Transducer descriptions of DNA code properties and undecidability of antimorphic problems ⋮ Descriptional Complexity of Error Detection ⋮ Randomized generation of error control codes with automata and transducers ⋮ Implementation of Code Properties via Transducers ⋮ Approximate NFA universality motivated by information theory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Codes defined by multiple sets of trajectories
• Rational equivalence relations
• Shuffle on trajectories: Syntactic constraints
• Transducers and the decidability of independence in free monoids
• Coding properties of DNA languages.
• Language equations, maximality and error-detection
• On properties of bond-free DNA languages
• Squaring transducers: An efficient procedure for deciding functionality and sequentiality.
• Trajectory-based codes
• Thin and slender languages
• A note on finite-valued and finitely ambiguous transducers
• Relations on free monoids, their independent sets, and codes¹
• Decidability of code properties
• Finite maximal solid codes

This page was built for publication: FORMAL DESCRIPTIONS OF CODE PROPERTIES: DECIDABILITY, COMPLEXITY, IMPLEMENTATION