All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 2 Next

Displaying 21 – 40 of 190

Showing per page

The communication hierarchy of time and space bounded parallel machines

Norbert Popély (2003)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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.

The Communication Hierarchy of Time and Space Bounded Parallel Machines

Norbert Popély (2010)

RAIRO - Theoretical Informatics and Applications

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.

The completely distributive lattice of machine invariant sets of infinite words

Aleksandrs Belovs, Jānis Buls (2007)

Discussiones Mathematicae - General Algebra and Applications

We investigate the lattice of machine invariant classes. This is an infinite completely distributive lattice but it is not a Boolean lattice. The length and width of it is c. We show the subword complexity and the growth function create machine invariant classes.

The compositional construction of Markov processes II

L. de Francesco Albasini, N. Sabadini, R. F. C. Walters (2011)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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

The compositional construction of Markov processes II

L. de Francesco Albasini, N. Sabadini, R. F.C. Walters (2011)

RAIRO - Theoretical Informatics and Applications

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

Currently displaying 21 – 40 of 190