Name
Abstract | ||
|---|---|---|
In this paper, we propose a model for measuring the reliability of the description of a language L by a deterministic finite automaton M. Intuitively, the reliability M exhibits when used for L is high if the 'difference' between L and the language T(M) accepted by M is small. Using this model, we prove that the savings in the number of states between a fully reliable and a less reliable representation cannot be bounded by any function, even if the unreliable descriptions are required to exceed any given fixed level of reliability. Furthermore, we show that, for a single regular language, there is a level of reliability such that any description exceeding this level is at least as big as the smallest DFA for the language. |
Year | Venue | Keywords |
|---|---|---|
2004 | Journal of Automata, Languages and Combinatorics | fixed level,m. intuitively,unreliable description,reliable representation,language l,reliability m,deterministic finite automaton,smallest dfa,single regular language,regular language,software reliability,finite automata,deterministic finite automata |
Field | DocType | Volume |
Quantum finite automata,Discrete mathematics,Two-way deterministic finite automaton,Deterministic automaton,Nondeterministic finite automaton,Deterministic finite automaton,Powerset construction,Algorithm,DFA minimization,Regular language,Mathematics | Journal | 9 |
Issue | Citations | PageRank |
2-3 | 5 | 0.51 |
References | Authors | |
7 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Martin Kappes | 1 | 166 | 20.28 |
| Chandra M. R. Kintala | 2 | 348 | 42.70 |