6533b85ffe1ef96bd12c24fc
RESEARCH PRODUCT
The complexity of probabilistic versus deterministic finite automata
Andris Ambainissubject
Discrete mathematicsNested wordDeterministic finite automatonDFA minimizationDeterministic automatonQuantum finite automataTwo-way deterministic finite automatonNondeterministic finite automatonω-automatonNonlinear Sciences::Cellular Automata and Lattice GasesComputer Science::Formal Languages and Automata TheoryMathematicsdescription
We show that there exists probabilistic finite automata with an isolated cutpoint and n states such that the smallest equivalent deterministic finite automaton contains \(\Omega \left( {2^{n\tfrac{{\log \log n}}{{\log n}}} } \right)\) states.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1996-01-01 |