The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
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...
In the XML standard, data are represented as unranked labeled
ordered trees. Regular unranked tree automata provide a useful
formalism for the validation of schemas enforcing regular structural
constraints on XML documents. However some concrete application
contexts need the expression of more general constraints than the
regular ones. In this paper we propose a new framework in which
context-free style structural constraints can be expressed and
validated. This framework is characterized by: (i)...
We give several new applications of the wreath product of forest algebras to the study of logics on trees. These include new simplified proofs of necessary conditions for definability in CTL and first-order logic with the ancestor relation; a sequence of identities satisfied by all forest languages definable in PDL; and new examples of languages outside CTL, along with an application to the question of what properties are definable in both CTL and LTL.
We formulate recursive characterizations of the class of elementary functions and the class of functions computable in polynomial space that do not require any explicit bounded scheme. More specifically, we use functions where the input variables can occur in different kinds of positions ?normal and safe? in the vein of the Bellantoni and Cook's characterization of the polytime functions.
We analyse the resilience of the quantum search algorithm in the presence of quantum noise modelled as trace preserving completely positive maps. We study the influence of noise on the computational complexity of the quantum search algorithm. We show that it is only for small amounts of noise that the quantum search algorithm is still more efficient than any classical algorithm.
A new proof of Maxfield’s theorem is given, using automata and results from Symbolic Dynamics. These techniques permit to prove that points that are near normality to base (resp. ) are also near normality to base (resp. ), and to study genericity preservation for non Lebesgue measures when going from one base to the other. Finally, similar results are proved to bases the golden mean and its square.
String rewriting reductions of the form , called
loops, are the most frequent cause of infinite reductions
(non- termination). Regarded as a model of computation, infinite
reductions are unwanted whence their static detection is important.
There are string rewriting systems which admit infinite reductions
although they admit no loops. Their non-termination is particularly
difficult to uncover. We present a few necessary conditions
for the existence of loops, and thus establish a means...
Currently displaying 1 –
20 of
44