%0 Conference Proceedings
%T One-Time Nondeterministic Computations
%+ Justus-Liebig-Universität Gießen = Justus Liebig University (JLU)
%A Holzer, Markus
%A Kutrib, Martin
%Z Part 2: Contributed Papers
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 19th International Conference on Descriptional Complexity of Formal Systems (DCFS)
%C Milano, Italy
%Y Giovanni Pighizzini
%Y Cezar Câmpeanu
%I Springer International Publishing
%3 Descriptional Complexity of Formal Systems
%V LNCS-10316
%P 177-188
%8 2017-07-03
%D 2017
%R 10.1007/978-3-319-60252-3_14
%Z Computer Science [cs]Conference papers
%X 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.
%G English
%Z TC 1
%Z WG 1.2
%2 https://inria.hal.science/hal-01657018/document
%2 https://inria.hal.science/hal-01657018/file/440206_1_En_14_Chapter.pdf
%L hal-01657018
%U https://inria.hal.science/hal-01657018
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG
%~ IFIP-DCFS
%~ IFIP-WG1-2
%~ IFIP-LNCS-10316