This paper discusses $n$-island finite automata whose transition graphs can be expressed as $n$-member sequences of islands $i_1,i_2,\cdots ,i_n$, where there is a bridge leaving $i_j$ and entering $i_{j+1}$ for each $1\le j\le n-1$. It concentrates its attention on even computation defined as any sequence of moves during which these automata make the same number of moves in each of the islands. Under the assumption that these automata work only in an evenly computational way, the paper proves its main result stating that $n$-island finite automata...

A general definition of a quantum predicate and quantum labelled transition systems for finite quantum computation systems is presented. The notion of a quantum predicate as a positive operator-valued measure is developed. The main results of this paper are a theorem about the existence of generalised predicates for quantum programs defined as completely positive maps and a theorem about the existence of a GSOS format for quantum labelled transition systems. The first theorem is a slight generalisation...

We investigate the possibility of extending Chrobak normal form to the probabilistic case. While in the nondeterministic case a unary automaton can be simulated by an automaton in Chrobak normal form without increasing the number of the states in the cycles, we show that in the probabilistic case the simulation is not possible by keeping the same number of ergodic states. This negative result is proved by considering the natural extension to the...

We investigate the possibility of extending Chrobak normal form to the probabilistic case. While in the nondeterministic case a unary automaton can be simulated by an automaton in Chrobak normal form without increasing the number of the states in the cycles, we show that in the probabilistic case the simulation is not possible by keeping the same number of ergodic states. This negative result is proved by considering the natural extension to the probabilistic case of Chrobak normal form, obtained...

We investigate the possibility of extending Chrobak normal form to the probabilistic case. While in the nondeterministic case a unary automaton can be simulated by an automaton in Chrobak normal form without increasing the number of the states in the cycles, we show that in the probabilistic case the simulation is not possible by keeping the same number of ergodic states. This negative result is proved by considering the natural extension to the...

We investigate the succinctness of several kinds of unary automata by studying their state complexity in accepting the family $\left\{L_m\right\}$ of cyclic languages, where $L_m=\left\{a^{km}\right|k\in \mathbb{N}\}$. In particular, we show that, for any $m$, the number of states necessary and sufficient for accepting the unary language $L_m$ with isolated cut point on one-way probabilistic finite automata is $p_1^{{\alpha }_1}+p_2^{{\alpha }_2}+\cdots +p_s^{{\alpha }_s}$, with $p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_s^{{\alpha }_s}$ being the factorization of $m$. To prove this result, we give a general state lower bound for accepting unary languages with isolated cut point on...

We investigate the succinctness of several kinds of unary automata by studying their state complexity in accepting the family {Lm} of cyclic languages, where Lm = akm | k ∈ N. In particular, we show that, for any m, the number of states necessary and sufficient for accepting the unary language Lm with isolated cut point on one-way probabilistic finite automata is $p_1^{{\alpha }_1}+p_2^{{\alpha }_2}+\cdots +p_s^{{\alpha }_s}$, with $p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_s^{{\alpha }_s}$ being the factorization of m. To prove this result, we give a general state lower bound for accepting unary languages...

We show that for an arbitrary Set-endofunctor T the generalized membership function given by a sub-cartesian transformation μ from T to the filter functor 𝔽 can be alternatively defined by the collection of subcoalgebras of constant T-coalgebras. Sub-natural transformations ε between any two functors S and T are shown to be sub-cartesian if and only if they respect μ. The class of T-coalgebras whose structure map factors through ε is shown to be a covariety if ε is a natural and sub-cartesian mono-transformation....

We show that, for any stochastic event $p$ of period $n$, there exists a measure-once one-way quantum finite automaton (1qfa) with at most $2\sqrt{6n}+25$ states inducing the event $ap+b$, for constants $a\>0$, $b\ge 0$, satisfying $a+b\le 1$. This fact is proved by designing an algorithm which constructs the desired 1qfa in polynomial time. As a consequence, we get that any periodic language of period $n$ can be accepted with isolated cut point by a 1qfa with no more than $2\sqrt{6n}+26$ states. Our results give added evidence of the strength of measure-once...

We show that, for any stochastic event p of period n, there exists a measure-once one-way quantum finite automaton (1qfa) with at most $2\sqrt{6n}+25$ states inducing the event ap+b, for constants a>0, b ≥ 0, satisfying a+b ≥ 1. This fact is proved by designing an algorithm which constructs the desired 1qfa in polynomial time. As a consequence, we get that any periodic language of period n can be accepted with isolated cut point by a 1qfa with no more than $2\sqrt{6n}+26$ states. Our results give added evidence of the...

The class of weak parallel machines is interesting, because it contains some realistic parallel machine models, especially suitable for pipelined computations. We prove that a modification of the bulk synchronous parallel (BSP) machine model, called decomposable BSP (dBSP), belongs to the class of weak parallel machines if restricted properly. We will also correct some earlier results about pipelined parallel Turing machines.

The class of weak parallel machines is interesting, because it contains some realistic parallel machine models, especially suitable for pipelined computations. We prove that a modification of the bulk synchronous parallel (BSP) machine model, called decomposable BSP (dBSP), belongs to the class of weak parallel machines if restricted properly. We will also correct some earlier results about pipelined parallel Turing machines.

In this work we study some probabilistic models for the random generation of words over a given alphabet used in the literature in connection with pattern statistics. Our goal is to compare models based on Markovian processes (where the occurrence of a symbol in a given position only depends on a finite number of previous occurrences) and the stochastic models that can generate a word of given length from a regular language under uniform distribution. We present some results that show the differences...