Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10334321 | Theoretical Computer Science | 2005 | 12 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Martin Kappes, Frank NieÃner,