6533b86ffe1ef96bd12cdb9f

RESEARCH PRODUCT

Non-constructive Methods for Finite Probabilistic Automata

Rūsiņš Freivalds

subject

Discrete mathematicsDeterministic finite automatonNested wordDFA minimizationDeterministic automatonAutomata theoryQuantum finite automataNondeterministic finite automatonω-automatonNonlinear Sciences::Cellular Automata and Lattice GasesComputer Science::Formal Languages and Automata TheoryMathematics

description

Size (the number of states) of finite probabilistic automata with an isolated cut-point can be exponentially smaller than the size of any equivalent finite deterministic automaton. The result is presented in two versions. The first version depends on Artin's Conjecture (1927) in Number Theory. The second version does not depend on conjectures but the numerical estimates are worse. In both versions the method of the proof does not allow an explicit description of the languages used. Since our finite probabilistic automata are reversible, these results imply a similar result for quantum finite automata.

yearjournalcountryeditionlanguage
2007-09-12
https://doi.org/10.1007/978-3-540-73208-2_18