6533b873fe1ef96bd12d5f64
RESEARCH PRODUCT
Regularity of one-letter languages acceptable by 2-way finite probabilistic automata
Janis Kanepssubject
Discrete mathematicsHigh probabilityProbabilistic finite automataComputer scienceProbabilistic automatondescription
R. Freivalds proved that the nonregular language {0m1m} can be recognized by 2-way probabilistic finite automata (2pfa) with arbitrarily high probability 1-e (e>0). We prove that such an effect is impossible for one-letter languages: every one-letter language acceptable by 2pfa with an isolated cutpoint is regular.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1991-01-01 |