Skip to Main content Skip to Navigation
Conference papers

One-Time Nondeterministic Computations

Abstract : We introduce the concept of one-time nondeterminism as a new kind of limited nondeterminism for finite state machines and pushdown automata. Roughly speaking, one-time nondeterminism means that at the outset the automaton is nondeterministic, but whenever it performs a guess, this guess is fixed for the rest of the computation. We characterize the computational power of one-time nondeterministic finite automata (OTNFAs) and one-time nondeterministic pushdown devices. Moreover, we study the descriptional complexity of these machines. For instance, we show that for an n-state OTNFA with a sole nondeterministic state, that is nondeterministic for only one input symbol, $(n+1)^n$ states are sufficient and necessary in the worst case for an equivalent deterministic finite automaton. In case of pushdown automata, the conversion of a nondeterministic to a one-time nondeterministic as well as the conversion of a one-time nondeterministic to a deterministic one turn out to be non-recursive, that is, the trade-offs in size cannot be bounded by any recursive function.
Document type :
Conference papers
Complete list of metadata
Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Wednesday, December 6, 2017 - 11:44:52 AM
Last modification on : Thursday, March 3, 2022 - 3:24:02 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



Markus Holzer, Martin Kutrib. One-Time Nondeterministic Computations. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. pp.177-188, ⟨10.1007/978-3-319-60252-3_14⟩. ⟨hal-01657018⟩



Record views


Files downloads