Multihead two-way probabilistic finite automata

DOI10.1007/3-540-59175-3_103zbMath1495.68124OpenAlexW1510102637MaRDI QIDQ5096345

Ioan I. Macarie

Publication date: 16 August 2022

Published in: LATIN '95: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-59175-3_103

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Classical models of computation (Turing machines, etc.) (68Q04)

Cites Work

• Decreasing the bandwidth of a transition matrix
• Making a fair roulette from a possibly biased coin
• The method of forced enumeration for nondeterministic automata
• Alternating multihead finite automata
• On tape-bounded complexity classes and multihead finite automata
• Space-bounded reducibility among combinatorial problems
• Transformational methods and their application to complexity problems
• Techniques for separating space complexity classes
• Relating refined space complexity classes
• Relationships between nondeterministic and deterministic tape complexities
• On non-determinacy in simple computing devices
• On two-way multihead automata
• Parallel computation for well-endowed rings and space-bounded probabilistic machines
• Nondeterministic Space is Closed under Complementation
• Computational Complexity of Probabilistic Turing Machines
• k + 1 Heads Are Better than k
• Finite state verifiers I
• Complexity of probabilistic versus deterministic automata
• Lower space bounds for randomized computation
• Computability by Probabilistic Turing Machines
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Multihead two-way probabilistic finite automata