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

Displaying 441 – 460 of 532

Showing per page

Time and space complexity of reversible pebbling

Richard Královič (2004)

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

This paper investigates one possible model of reversible computations, an important paradigm in the context of quantum computing. Introduced by Bennett, a reversible pebble game is an abstraction of reversible computation that allows to examine the space and time complexity of various classes of problems. We present a technique for proving lower and upper bounds on time and space complexity for several types of graphs. Using this technique we show that the time needed to achieve optimal space for...

Time and space complexity of reversible pebbling

Richard Královič (2010)

RAIRO - Theoretical Informatics and Applications

This paper investigates one possible model of reversible computations, an important paradigm in the context of quantum computing. Introduced by Bennett, a reversible pebble game is an abstraction of reversible computation that allows to examine the space and time complexity of various classes of problems. We present a technique for proving lower and upper bounds on time and space complexity for several types of graphs. Using this technique we show that the time needed to achieve optimal space for...

Tree inclusion problems

Patrick Cégielski, Irène Guessarian, Yuri Matiyasevich (2008)

RAIRO - Theoretical Informatics and Applications

Given two trees (a target T and a pattern P) and a natural number w, window embedded subtree problems consist in deciding whether P occurs as an embedded subtree of T and/or finding the number of size (at most) w windows of T which contain pattern P as an embedded subtree. P is an embedded subtree of T if P can be obtained by deleting some nodes from T (if a node v is deleted, all edges adjacent to v are also deleted, and outgoing edges are replaced by edges going from the parent of v (if it exists)...

Tuning the Zhu-Takaoka string matching algorithm and experimental results

Thomas Berry, Somasundaram Ravindran (2002)

Kybernetika

In this paper we present experimental results for string matching algorithms which have a competitive theoretical worst case run time complexity. Of these algorithms a few are already famous for their speed in practice, such as the Boyer–Moore and its derivatives. We chose to evaluate the algorithms by counting the number of comparisons made and by timing how long they took to complete a given search. Using the experimental results we were able to introduce a new string matching algorithm and compared...

Un nuevo resultado sobre la complejidad del problema del p-centro.

José Andrés Moreno Pérez (1990)

Trabajos de Investigación Operativa

Sea G un grafo no dirigido con n vértices y m aristas. Un p-Centro de G es un conjunto de p puntos en el que se minimiza la distancia al vértice más lejano. Esta distancia mínima es el p-Radio de G. Un Centro Local es un punto c a la misma distancia (llamada rango del centro local) de un conjunto no vacío de vértices que no son todos accesibles a través de un mismo vértice adyacente a c. Todo p-radio es el rango de algún centro local, por tanto, para resolver el problema del p-centro basta encontrar...

Unambiguous erasing morphisms in free monoids

Johannes C. Schneider (2010)

RAIRO - Theoretical Informatics and Applications

This paper discusses the fundamental combinatorial question of whether or not, for a given string α, there exists a morphism σ such that σ is unambiguous with respect to α, i.e. there exists no other morphism τ satisfying τ(α) = σ(α). While Freydenberger et al. [Int. J. Found. Comput. Sci. 17 (2006) 601–628] characterise those strings for which there exists an unambiguous nonerasing morphism σ, little is known about the unambiguity of erasing morphisms, i.e. morphisms that map symbols...

Currently displaying 441 – 460 of 532