Paper Info
Title
Formal Descriptions Of Code Properties: Decidability, Complexity, Implementation
Abstract
The branch of coding theory that is based on formal languages has produced several methods for defining code properties, including word relations, dependence systems, implicational conditions, trajectories, and language inequations. Of those, the latter three can be viewed as formal methods in the sense that a certain formal expression can be used to denote a code property. Here we present a formal method which is based on transducers. Each transducer of a certain type defines/describes a desired code property. The method provides simple and uniform decision procedures for the basic questions of property satisfaction and maximality for regular languages. Our work includes statements about the hardness of deciding some of the problems involved. It turns out that maximality can be hard to decide even for "classical" code properties of finite languages. We also present an initial implementation of a LAnguage SERver capable of deciding the satisfaction problem for a given transducer code property and regular language.
Year
DOI
Venue
2012
10.1142/S0129054112400059
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
Keywords
Field
DocType
Automata, codes, complexity, decidability, descriptions, implementation, languages, maximality, properties, transducers
Programming language,Decidability,Theoretical computer science,Coding theory,Formal methods,Regular language,Code (cryptography),Discrete mathematics,Combinatorics,Formal language,Automaton,Cone (formal languages),Mathematics
Journal
Volume
Issue
ISSN
23
1
0129-0541
Citations 
PageRank 
References 
10
0.87
14
Authors
2
Name
Order
Citations
PageRank
Krystian Dudzinski1100.87
Stavros Konstantinidis228331.10