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 52 Next

Displaying 1021 – 1040 of 2186

Showing per page

New applications of the wreath product of forest algebras

Howard Straubing (2013)

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

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.

New recursive characterizations of the elementary functions and the functions computable in polynomial space.

I. Oitavem (1997)

Revista Matemática de la Universidad Complutense de Madrid

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.

Noise effects in the quantum search algorithm from the viewpoint of computational complexity

Piotr Gawron, Jerzy Klamka, Ryszard Winiarczyk (2012)

International Journal of Applied Mathematics and Computer Science

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.

Non literal tranducers and some problems of normality

François Blanchard (1993)

Journal de théorie des nombres de Bordeaux

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 p k (resp. p ) are also near normality to base p (resp. p k ), 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.

Non-looping string rewriting

Alfons Geser, Hans Zantema (1999)

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

Non-Looping String Rewriting

Alfons Geser, Hans Zantema (2010)

RAIRO - Theoretical Informatics and Applications

String rewriting reductions of the form t → R + u t v , 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 1021 – 1040 of 2186