Succinct representations of languages by DFA with different levels of reliability

In this paper, we propose qualitative measures for the reliability of representations of languages by deterministic finite automata. We analyze the relationships between different qualitative features and investigate tradeoffs between different qualitative levels of reliability. Furthermore, we prov...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2005-02, Vol.330 (2), p.299-310
Main Authors: Kappes, Martin, Nießner, Frank
Format: Article
Language:English
Subjects:
Applied sciences
Automata. Abstract machines. Turing machines
Computer science
control theory
systems
Descriptional complexity
Exact sciences and technology
Finite automata
Language theory and syntactical analysis
Software reliability
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we propose qualitative measures for the reliability of representations of languages by deterministic finite automata. We analyze the relationships between different qualitative features and investigate tradeoffs between different qualitative levels of reliability. Furthermore, we prove that the savings in the number of states between representations having different qualitative features cannot be bounded by any function. These results hold even when the descriptions are required to exceed any given fixed level of quantified reliability.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2004.04.012