Journal article

Publication year: 2019

Pages: 1069-1089

Journal: International Journal of Foundations of Computer Science

Volume number: 30

Issue number: 6-7

ISSN: 0129-0541

eISSN: 1793-6373

Open access status: Green

DOI Link: https://doi.org/10.1142/S012905411940029X

Publisher: World Scientific Publishing

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 computation 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.

Harvard Citation style: Holzer, M. and Kutrib, M. (2019) One-Time Nondeterministic Computations, International Journal of Foundations of Computer Science, 30(6-7), pp. 1069-1089. https://doi.org/10.1142/S012905411940029X

APA Citation style: Holzer, M., & Kutrib, M. (2019). One-Time Nondeterministic Computations. International Journal of Foundations of Computer Science. 30(6-7), 1069-1089. https://doi.org/10.1142/S012905411940029X