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

https://hal.inria.fr/hal-01657018
Contributor : Hal Ifip <>
Submitted on : Wednesday, December 6, 2017 - 11:44:52 AM
Last modification on : Monday, February 26, 2018 - 1:40:02 PM

File

440206_1_En_14_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

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⟩

Share

Metrics

Record views

121

Files downloads

109