Multihead two-way probabilistic finite automata (extended abstract)
type: Item
instance of: scholarly article
title: Multihead two-way probabilistic finite automata
zbMATH Open document ID: 1495.68124
DOI: 10.1007/3-540-59175-3_103
author: Ioan I. Macarie
published in: LATIN '95: Theoretical Informatics
publication date: 2022-08-16T00:00:00Z
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q04
Mathematics Subject Classification ID: 68Q10
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 7572156
MaRDI profile type: MaRDI publication profile
full work available at URL: 3-540-59175-3 103
OpenAlex ID: W1510102637
cites work: Parallel computation for well-endowed rings and space-bounded probabilistic machines
cites work: Making a fair roulette from a possibly biased coin
cites work: Finite state verifiers I
cites work: Lower space bounds for randomized computation
cites work: Q3947125
cites work: Complexity of probabilistic versus deterministic automata
cites work: Computational Complexity of Probabilistic Turing Machines
cites work: On non-determinacy in simple computing devices
cites work: On two-way multihead automata
cites work: Nondeterministic Space is Closed under Complementation
cites work: Space-bounded reducibility among combinatorial problems
cites work: Q3912025
cites work: Q3706503
cites work: Q3735080
cites work: Q4266534
cites work: Alternating multihead finite automata
cites work: Q4043014
cites work: Q5180413
cites work: Decreasing the bandwidth of a transition matrix
cites work: Transformational methods and their application to complexity problems
cites work: Q3885190
cites work: Q5643915
cites work: Computability by Probabilistic Turing Machines
cites work: Relationships between nondeterministic and deterministic tape complexities
cites work: Relating refined space complexity classes
cites work: Techniques for separating space complexity classes
cites work: Q4139697
cites work: On tape-bounded complexity classes and multihead finite automata
cites work: The method of forced enumeration for nondeterministic automata
cites work: Q5562601
cites work: k + 1 Heads Are Better than k
Recommended article: Multihead two-way probabilistic finite automata
Recommended article: A NOTE ON MULTIHEAD FINITE-STATE AUTOMATA
Recommended article: Q5186739
Recommended article: On the structure of log-space probabilistic complexity classes (extended abstract)
Recommended article: On the Structure of Logspace Probabilistic Complexity Classes
description: scientific article; zbMATH DE number 7572156