Succinct Representations of Languages by DFA With Different Levels of Reliability.
Martin Kappes, Frank Nießner · DCFS · 2003
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.