Wyniki wyszukiwania - BazTech

1

Algebraic Characterization of the Class of Languages Recognized by Measure Only Quantum Automata

Comin C.

Fundamenta Informaticae

|

2014

|

Vol. 134, nr 3/4

335--353

EN

We study a model of one-way quantum automaton where only measurement operations are allowed (MON-1QFA). We give an algebraic characterization of LMO(Σ), showing that the syntactic monoids of the languages in LMO(Σ) are exactly the J-trivial literally idempotent syntactic monoids, where J is the Green’s relation determined by two-sided ideals. We also prove that LMO(Σ) coincides with the literal variety of literally idempotent piecewise testable languages. This allows us to prove the existence of a polynomial-time algorithm for deciding whether a regular language belongs to LMO(Σ).

2

Bisimulation relation for selected types of probabilistic and quantum automata

Siedlecka-Lamch O.

Scientific Issues of Jan Długosz University in Częstochowa. Mathematics

|

2011

|

Vol. 16

135--140

EN

The first step to make transitional systems more efficient is to minimize the number of their states. A bisimulation relation is a mathematical tool that helps in searching for equivalent systems, what is useful in the minimization of algorithms. For two transition systems bisimulation is a binary relation associating systems which behave in the same way in the sense that one system simulates the other and viceversa. The definition for classical systems is clear and simple, but what happens with nondeterministic, probabilistic and quantum systems? This will be the main topic of this article.

3

A minimization algorithm of 1-way quantum finite automata

Siedlecka-Lamch O.

Metody Informatyki Stosowanej

|

2010

|

nr 4 (24)

73-79

EN

A minimization of finite automata is important for designing of computer's hardware and software. A finite automata can be a model of any system with finite number of states. A limitation of number of states will save resources and time. In this article 1-way quantum finite automata is presented. We describe its characteristics, behaviour and languages accepted by it. This type of automata can be in future exploited to design and checking the behaviour of quantum systems, in lexical anaiyzer of a compiler, that will be used on quantum computers, or in verification systems. Also in this case Iimitation of states will save resources. The article holds formulated definition of indistinguishableness relation for 1-way quantum finite automata, on base of which minimization algorithm was created. Additionally, the algorithm 's complexity analysis and example of behaviour is holded.

4

Behaviours of Unary Quantum Automata

Bianchi M.P., Palano B.

Fundamenta Informaticae

|

2010

|

Vol. 104, nr 1/2

1-15

EN

We study the stochastic events induced by MM-qfa's working on unary alphabets. We give two algorithms for unary MM-qfa's: the first computes the dimension of the ergodic and transient components of the non halting subspace, while the second tests whether the induced event is d-periodic. These algorithms run in polynomial time whenever the MM-qfa given in input has complex amplitudes with rational components. We also characterize the recognition power of unary MM-qfa's, by proving that any unary regular language can be accepted by a MM-qfa with constant cut point and isolation. Yet, the amount of states of the resulting MM-qfa is linear in the size of the corresponding minimal dfa. We also single out families of unary regular languages for which the size of the accepting MM-qfa's can be exponentially decreased.