Infinite vs. Finite Space-Bounded Randomized Computations
METADATA ONLY
Loading...
Author / Creator
Date
2009
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
Probabilistic computations can be very powerful with respect to space complexity, e.g. for logarithmic space, zero probability of error is equivalent to nondeterminism. This power, however, depends on the possibility of infinite computations. A natural open question is if this feature is necessary. We answer the question for sweeping finite automata (SFAs), i.e. two-way finite automata that can change the direction of head motion at endmarkers only. We show that zero probability of error SFAs allowing infinite computations can be exponentially more succinct than zero probability of error SFAs forbidding them. We also provide a strengthened form of this result showing that forbidding infinite computations can not be traded for the more powerful bounded-error probabilistic model. To prove our results, we introduce a technique for proving lower bounds on space complexity of SFAs that generalizes the notion of generic words discovered by M. Sipser © 2009 IEEE.
Permanent link
Publication status
published
External links
Editor
Book title
Computational Complexity, 2009. CCC '09. 24th Annual IEEE Conference on
Journal / series
Volume
Pages / Article No.
316 - 325
Publisher
IEEE
Event
24th Annual IEEE Conference on Computational Complexity
Edition / version
Methods
Geographic location
Date collected
Date created
Subject
Automata; Complexity
Organisational unit
Notes
Funding Info about funding
Related publications and datasets
Is previous version of: