scientific article
From MaRDI portal
Publication:3947125
zbMath0486.68045MaRDI QIDQ3947125
Publication date: 1981
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
real timeprobabilistic Turing machinesemptiness problemrecognition of languagesfinite nondeterministic automatafinite probabilistic automata with isolated cut-pointshead-to-head jumpspolynomial time deterministic turing machinespace complexities
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (44)
Unary probabilistic and quantum automata on promise problems ⋮ Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations ⋮ Interactive proof systems with public coin: Lower space bounds and hierarchies of complexity classes ⋮ Multiple Usage of Random Bits in Finite Automata ⋮ On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes ⋮ Time-Space Complexity Advantages for Quantum Computing ⋮ Infinite vs. finite size-bounded randomized computations ⋮ The Effect of Tossing Coins in Omega-Automata ⋮ Affine automata verifiers ⋮ Uncountable realtime probabilistic classes ⋮ On some variations of two-way probabilistic finite automata models ⋮ Counting with Probabilistic and Ultrametric Finite Automata ⋮ Classical and Quantum Counter Automata on Promise Problems ⋮ Interference as a computational resource: a tutorial ⋮ Size complexity of rotating and sweeping automata ⋮ Lifting query complexity to time-space complexity for two-way finite automata ⋮ Modeling of RNA secondary structures using two-way quantum finite automata ⋮ The complexity of debate checking ⋮ Decreasing the bandwidth of a transition matrix ⋮ Multihead two-way probabilistic finite automata ⋮ Lower time bounds for randomized computation ⋮ A note on two-way probabilistic automata ⋮ Unbounded-error quantum computation with small space bounds ⋮ On partially blind multihead finite automata. ⋮ A probabilistic model of computing with words ⋮ Probabilistic Acceptors for Languages over Infinite Words ⋮ Group Input Machine ⋮ Unnamed Item ⋮ Properties of probabilistic pushdown automata ⋮ A lower bound for probabilistic algorithms for finite state machines ⋮ Probabilistic rebound Turing machines ⋮ Probabilistic Büchi Automata with Non-extremal Acceptance Thresholds ⋮ Multihead two-way probabilistic finite automata ⋮ Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice ⋮ Efficient probability amplification in two-way quantum finite automata ⋮ Uncountable classical and quantum complexity classes ⋮ Size Complexity of Two-Way Finite Automata ⋮ Closure properties of the classes of sets recognized by space-bounded two-dimensional probabilistic Turing machines ⋮ A note on two-dimensional probabilistic Turing machines ⋮ Randomised algorithms ⋮ A note on two-dimensional probabilistic finite automata ⋮ Two-way finite automata with quantum and classical states. ⋮ Computation with multiple CTCs of fixed length and width ⋮ On the undecidability of probabilistic planning and related stochastic optimization problems
This page was built for publication:
