|
Browse All Reviews > Theory Of Computation (F) > Computation By Abstract Devices (F.1) > Modes Of Computation (F.1.2) > Alternation And Nondeterminism (F.1.2...)
|
|
|
|
|
|
|
|
|
1-10 of 12
Reviews about "Alternation And Nondeterminism (F.1.2...)":
|
Date Reviewed |
|
NFA reduction algorithms by means of regular inequalities Champarnaud J., Coulon F. Theoretical Computer Science 327(3): 241-253, 2004. Type: Article, Reviews: (2 of 2)
Champarnaud and Coulon deal with the problem of reducing the number of states of a given nondeterministic finite automaton (NFA) A. For deterministic automata, it is well known that the number of states can actually ...
|
Aug 31 2006 |
|
Defining fairness Völzer H., Varacca D., Kindler E. In CONCUR 2005 -- Concurrency Theory: 16th International Conference, San Francisco, CA, August 23-26, 2005. Proceedings (LNCS 3653). London, UK: Springer-Verlag, 2005. Type: Book Chapter
There is not a prevailing definition of fairness, but most definitions attempt to ensure that every transition of a system that is enabled sufficiently often is executed sufficiently often. The authors of this paper present a new defin...
|
Jun 7 2006 |
|
NFA reduction algorithms by means of regular inequalities Champarnaud J., Coulon F. Theoretical Computer Science 327(3): 241-253, 2004. Type: Article, Reviews: (1 of 2)
This paper investigates the nondeterministic polynomial time (NP) hard problem of producing a minimal nondeterministic finite automata (NFA). This problem is widely known to be in polynomial time (P) for deterministic finite state auto...
|
May 13 2005 |
|
A hierarchy based on output multiplicity Naik A., Rogers J., Royer J., Selman A. (ed) Theoretical Computer Science 207(1): 131-157, 1998. Type: Article
A refinement of a partial multivalued function f is a function g that is undefined on all inputs on which f is undefined (that is, has no outputs), and on all inputs on which <
|
May 1 1999 |
|
ASPACE(o(log log n)) is regular Iwama K. SIAM Journal on Computing 22(1): 136-146, 1993. Type: Article
Regular sets are accepted by deterministic or nondeterministic finite-state automata, which are deterministic or nondeterministic Turing machines (DTMs and NTMs) using constant space. It is known that even if the NTM is allowed
|
Jan 1 1994 |
|
Communication for alternating machines Slobodová A. Acta Informatica 29(5): 425-441, 1992. Type: Article
Alternating polynomial-time Turing machines, as introduced by Chandra, Kozen, and Stockmeyer [1], are polynomial-time machines that can alternate between universal blocks (in which a node accepts if all its children accept) and existe...
|
Sep 1 1993 |
|
Multiplicities: a deterministic view of nondeterminism Karhumäki J. Theoretical Computer Science 98(1): 15-25, 1992. Type: Article
The behavior of corresponding deterministic and nondeterministic devices may be markedly different, and problems that are decidable for deterministic devices are frequently undecidable for nondeterministic devices. A nondeterministic p...
|
Jul 1 1993 |
|
Generalizations of Opt P to the polynomial hierarchy Krentel M. Theoretical Computer Science 97(2): 183-198, 1992. Type: Article
Classical complexity theory has concentrated on studying problems that have yes/no answers--that is, 0-1 functions. Both classical recursive function theory and optimization theory have studied more general functions, however....
|
Jul 1 1993 |
|
Combining angels, demons and miracles in program specifications Back R., von Wright J. Theoretical Computer Science 100(2): 365-383, 1992. Type: Article
In a previous paper[1], the authors defined a specification language C within the complete lattice of monotonic predicate transformers using only simple primitive commands and functional composition in addition to meets and joins. It w...
|
Jul 1 1993 |
|
A note on real-time one-way alternating multicounter machines Inoue K., Ito A., Takanami I. Theoretical Computer Science 88(2): 287-296, 1991. Type: Article
In a one-way multicomputer machine, each pushdown store has a single symbol in its tape alphabet, making each store a counter. A one-way alternating multicounter machine M divides the states into disjoint sets of uni...
|
Jan 1 1993 |
|
|
|
|
|
|