@inproceedings{75a216e6646945ddb723cc0804edb864,
title = "The complexity of probabilistic versus deterministic finite automata",
abstract = "We show that there exists probabflistic finite automata with an isolated cutpoint and n states such that the smallest equivalent deterministic finite automaton contains (Formula presented) states.",
keywords = "Automata theory, Probabilistic finite automata, The complexity of finite automata",
author = "Andris Ambainis",
note = "Publisher Copyright: {\textcopyright} 1996 Springer-Verlag. All rights reserved.; 7th International Symposium on Algorithms and Computation, ISAAC 1996 ; Conference date: 16-12-1996 Through 18-12-1996",
year = "1996",
doi = "10.1007/bfb0009499",
language = "English",
isbn = "3540620486",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "233--238",
editor = "Tetsuo Asano and Yoshihide Igarashi and Hiroshi Nagamochi and Satoru Miyano and Subhash Suri",
booktitle = "Algorithms and Computation - 7th International Symposium, ISAAC 1996, Proceedings",
address = "Germany",
}