Loading [MathJax]/extensions/MathZoom.js
We describe the communicating alternating machines and their simulation. We show that, in the case of communicating alternating machines which are bounded, simultaneously, by polynomial time and logarithmic space, the use of three communication levels instead of two does not increase computational power of communicating alternating machines. This resolves an open problem [2] concerning the exact position of machines with three communication levels in the hierarchy.
We describe the communicating alternating machines and their
simulation. We show that, in the case of communicating alternating
machines which are bounded, simultaneously, by polynomial time and
logarithmic space, the use of three communication levels instead
of two does not increase computational power of communicating
alternating machines. This resolves an open problem [2]
concerning the exact position of machines with three communication
levels in the hierarchy.
We add sequential operations to the categorical algebra of weighted and Markov automata introduced in [L. de Francesco Albasini, N. Sabadini and R.F.C. Walters,
arXiv:0909.4136]. The extra expressiveness of the algebra permits the description of hierarchical systems, and ones with evolving geometry. We make a comparison with the probabilistic automata of Lynch et al. [SIAM J. Comput. 37 (2007) 977–1013].
We add sequential operations to the categorical algebra of weighted and
Markov automata introduced in [L. de Francesco Albasini, N. Sabadini and R.F.C. Walters,
arXiv:0909.4136]. The extra
expressiveness of
the algebra permits the description of hierarchical systems, and ones with
evolving geometry. We make a comparison with the probabilistic automata of
Lynch et al. [SIAM J. Comput.37 (2007) 977–1013].
This paper investigates one possible model of reversible computations, an important paradigm in the context of quantum computing. Introduced by Bennett, a reversible pebble game is an abstraction of reversible computation that allows to examine the space and time complexity of various classes of problems. We present a technique for proving lower and upper bounds on time and space complexity for several types of graphs. Using this technique we show that the time needed to achieve optimal space for...
This paper investigates one possible model of reversible computations, an
important paradigm in the context of quantum computing. Introduced by
Bennett, a reversible pebble game is an
abstraction of reversible computation that allows to examine the space and
time complexity of various classes of problems. We present a technique
for proving lower and upper bounds on time and space complexity for several
types of graphs. Using this technique we show that the time needed to
achieve optimal space for...
Currently displaying 1 –
11 of
11