Displaying similar documents to “On the state complexity of semi-quantum finite automata”

Quantum finite automata with control language

Carlo Mereghetti, Beatrice Palano (2006)

RAIRO - Theoretical Informatics and Applications

Similarity:

Bertoni  introduced in (2003) 1–20 a new model of 1-way quantum finite automaton (1qfa) called . This model, whose recognizing power is exactly the class of regular languages, generalizes main models of 1qfa's proposed in the literature. Here, we investigate some properties of 1qfc's. In particular, we provide algorithms for constructing 1qfc's accepting the inverse homomorphic images and quotients of languages accepted by 1qfc's. Moreover, we give instances ...

Local Transition Functions of Quantum Turing Machines

Masanao Ozawa, Harumichi Nishimura (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Foundations of the notion of quantum Turing machines are investigated. According to Deutsch's formulation, the time evolution of a quantum Turing machine is to be determined by the local transition function. In this paper, the local transition functions are characterized for fully general quantum Turing machines, including multi-tape quantum Turing machines, extending the results due to Bernstein and Vazirani.

Natural quantum operational semantics with predicates

Marek Sawerwain, Roman Gielerak (2008)

International Journal of Applied Mathematics and Computer Science

Similarity:

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

Note on the succinctness of deterministic, nondeterministic, probabilistic and quantum finite automata

Carlo Mereghetti, Beatrice Palano, Giovanni Pighizzini (2001)

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

Similarity:

We investigate the succinctness of several kinds of unary automata by studying their state complexity in accepting the family { L m } of cyclic languages, where L m = { a k m | k } . 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 α 1 + p 2 α 2 + + p s α s , with p 1 α 1 p 2 α 2 p s α s being the factorization of m . To prove this result, we give a general state lower bound for accepting unary languages with isolated...