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. |
Year | DOI | Venue |
---|---|---|
2003 | 10.1016/j.tcs.2004.04.012 | Theoretical Computer Science - Descriptional complexity of formal systems |
Keywords | DocType | Volume |
fixed level,different level,qualitative measure,succinct representation,different qualitative,different qualitative level,Software reliability,deterministic finite automaton,Descriptional complexity,Finite automata,different qualitative feature | Conference | 330 |
Issue | ISSN | Citations |
2 | 0304-3975 | 3 |
PageRank | References | Authors |
0.42 | 5 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Martin Kappes | 1 | 166 | 20.28 |
Frank Nießner | 2 | 4 | 2.13 |