The complexity of probabilistic versus deterministic finite automata

Andris Ambainis

doi:10.1007/bfb0009499

The complexity of probabilistic versus deterministic finite automata

Andris Ambainis^*

^*Corresponding author for this work

University of Latvia

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › Research › peer-review

24 Citations (Scopus)

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.

Original language	English
Title of host publication	Algorithms and Computation - 7th International Symposium, ISAAC 1996, Proceedings
Editors	Tetsuo Asano, Yoshihide Igarashi, Hiroshi Nagamochi, Satoru Miyano, Subhash Suri
Publisher	Springer Verlag
Pages	233-238
Number of pages	6
ISBN (Print)	3540620486, 9783540620488
DOIs	https://doi.org/10.1007/bfb0009499
Publication status	Published - 1996
Externally published	Yes
Event	7th International Symposium on Algorithms and Computation, ISAAC 1996 - Osaka, Japan Duration: 16 Dec 1996 → 18 Dec 1996

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1178
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	7th International Symposium on Algorithms and Computation, ISAAC 1996
Country/Territory	Japan
City	Osaka
Period	16/12/96 → 18/12/96

Keywords

Automata theory
Probabilistic finite automata
The complexity of finite automata

Access to Document

10.1007/bfb0009499

Cite this

Ambainis, A. (1996). The complexity of probabilistic versus deterministic finite automata. In T. Asano, Y. Igarashi, H. Nagamochi, S. Miyano, & S. Suri (Eds.), Algorithms and Computation - 7th International Symposium, ISAAC 1996, Proceedings (pp. 233-238). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1178). Springer Verlag. https://doi.org/10.1007/bfb0009499

Ambainis, Andris. / The complexity of probabilistic versus deterministic finite automata. Algorithms and Computation - 7th International Symposium, ISAAC 1996, Proceedings. editor / Tetsuo Asano ; Yoshihide Igarashi ; Hiroshi Nagamochi ; Satoru Miyano ; Subhash Suri. Springer Verlag, 1996. pp. 233-238 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@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",

}

Ambainis, A 1996, The complexity of probabilistic versus deterministic finite automata. in T Asano, Y Igarashi, H Nagamochi, S Miyano & S Suri (eds), Algorithms and Computation - 7th International Symposium, ISAAC 1996, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1178, Springer Verlag, pp. 233-238, 7th International Symposium on Algorithms and Computation, ISAAC 1996, Osaka, Japan, 16/12/96. https://doi.org/10.1007/bfb0009499

The complexity of probabilistic versus deterministic finite automata. / Ambainis, Andris.
Algorithms and Computation - 7th International Symposium, ISAAC 1996, Proceedings. ed. / Tetsuo Asano; Yoshihide Igarashi; Hiroshi Nagamochi; Satoru Miyano; Subhash Suri. Springer Verlag, 1996. p. 233-238 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1178).

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › Research › peer-review

TY - GEN

T1 - The complexity of probabilistic versus deterministic finite automata

AU - Ambainis, Andris

PY - 1996

Y1 - 1996

N2 - 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.

AB - 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.

KW - Automata theory

KW - Probabilistic finite automata

KW - The complexity of finite automata

UR - https://www.scopus.com/pages/publications/84990182878

U2 - 10.1007/bfb0009499

DO - 10.1007/bfb0009499

M3 - Conference paper

AN - SCOPUS:84990182878

SN - 3540620486

SN - 9783540620488

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 233

EP - 238

BT - Algorithms and Computation - 7th International Symposium, ISAAC 1996, Proceedings

A2 - Asano, Tetsuo

A2 - Igarashi, Yoshihide

A2 - Nagamochi, Hiroshi

A2 - Miyano, Satoru

A2 - Suri, Subhash

PB - Springer Verlag

T2 - 7th International Symposium on Algorithms and Computation, ISAAC 1996

Y2 - 16 December 1996 through 18 December 1996

ER -

Ambainis A. The complexity of probabilistic versus deterministic finite automata. In Asano T, Igarashi Y, Nagamochi H, Miyano S, Suri S, editors, Algorithms and Computation - 7th International Symposium, ISAAC 1996, Proceedings. Springer Verlag. 1996. p. 233-238. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/bfb0009499

The complexity of probabilistic versus deterministic finite automata

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this