Formal descriptions of code properties: decidability, complexity, implementation

DOI10.1142/S0129054112400059MaRDI QIDQ2909182zbMATH OpenFDO

Authors Krystian Dudzinski, Stavros Konstantinidis

Publication date 30 August 2012

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

zbMATH Keywords

complexitypropertiesautomatacodesdecidabilityimplementationtransducerslanguagesmaximalitydescriptions

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Decidability of code properties
• Decidability of code properties
• Formalization of Properties of Functional Programs
• Descriptional complexity of formal systems
• Descriptological foundations of programming
• scientific article; zbMATH DE number 826059
• scientific article; zbMATH DE number 1302020
• Toward complete programming language descriptions that are both formal and understandable
• scientific article; zbMATH DE number 51766

Cites work

• scientific article; zbMATH DE number 3943051 (Why is no real title available?)
• scientific article; zbMATH DE number 50943 (Why is no real title available?)
• A note on finite-valued and finitely ambiguous transducers
• Automata theory: Its past and future
• Codes defined by multiple sets of trajectories
• Coding properties of DNA languages.
• Decidability of code properties
• Finite maximal solid codes
• Language equations, maximality and error-detection
• On properties of bond-free DNA languages
• Rational equivalence relations
• Relations on free monoids, their independent sets, and codes¹
• Shuffle on trajectories: Syntactic constraints
• Squaring transducers: An efficient procedure for deciding functionality and sequentiality.
• Thin and slender languages
• Trajectory-based codes
• Transducers and the decidability of independence in free monoids

Cited in

(12)

• Symbolic manipulation of code properties
• On the maximality of languages with combined types of code properties
• Theoretical and implementational aspects of the formal language server (LaSer)
• Descriptional complexity of error detection
• Approximate NFA universality motivated by information theory
• scientific article; zbMATH DE number 51766 (Why is no real title available?)
• scientific article; zbMATH DE number 826059 (Why is no real title available?)
• Implementation of code properties via transducers
• Methods for relativizing properties of codes
• Approximate NFA universality and related problems motivated by information theory
• Randomized generation of error control codes with automata and transducers
• Block languages and their bitmap representations

This page was built for publication: Formal descriptions of code properties: decidability, complexity, implementation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2909182)