Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Browse by topic Browse by titles Authors Reviewers Browse by issue Browse Help
Search
  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...)  
 
Options:
 
  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
 
 
 
Display per page
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy