A note on two-way probabilistic automata

DOI10.1016/0020-0190(92)90119-GzbMath0769.68068WikidataQ127310087 ScholiaQ127310087MaRDI QIDQ1195495

Jie Wang

Publication date: 6 December 1992

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

Markov chaindeterministic context-sensitive languagestwo-way probabilistic finite state automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (6)

Infinite vs. finite size-bounded randomized computations ⋮ Probabilistic rebound Turing machines ⋮ Closure properties of the classes of sets recognized by space-bounded two-dimensional probabilistic Turing machines ⋮ A note on two-dimensional probabilistic Turing machines ⋮ A note on two-dimensional probabilistic finite automata ⋮ CLOSURE PROPERTY OF PROBABILISTIC TURING MACHINES AND ALTERNATING TURING MACHINES WITH SUBLOGARITHMIC SPACES

Cites Work

• A lower bound for probabilistic algorithms for finite state machines
• Matrix tree theorems
• Alternating Pushdown and Stack Automata
• A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
• Estimating a probability using finite memory
• Probabilistic automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A note on two-way probabilistic automata