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

Page 1 Next

Displaying 1 – 20 of 78

Showing per page

Factoring and testing primes in small space

Viliam Geffert, Dana Pardubská (2013)

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

We discuss how much space is sufficient to decide whether a unary given number n is a prime. We show that O(log log n) space is sufficient for a deterministic Turing machine, if it is equipped with an additional pebble movable along the input tape, and also for an alternating machine, if the space restriction applies only to its accepting computation subtrees. In other words, the language is a prime is in pebble–DSPACE(log log n) and also in accept–ASPACE(log log n). Moreover, if the given n is...

Feedback, trace and fixed-point semantics

P. Katis, Nicoletta Sabadini, Robert F. C. Walters (2002)

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

We introduce a notion of category with feedback-with-delay, closely related to the notion of traced monoidal category, and show that the Circ construction of [15] is the free category with feedback on a symmetric monoidal category. Combining with the Int construction of Joyal et al. [12] we obtain a description of the free compact closed category on a symmetric monoidal category. We thus obtain a categorical analogue of the classical localization of a ring with respect to a multiplicative subset....

Feedback, trace and fixed-point semantics

P. Katis, Nicoletta Sabadini, Robert F.C. Walters (2010)

RAIRO - Theoretical Informatics and Applications

We introduce a notion of category with feedback-with-delay, closely related to the notion of traced monoidal category, and show that the Circ construction of [15] is the free category with feedback on a symmetric monoidal category. Combining with the Int construction of Joyal et al. [12] we obtain a description of the free compact closed category on a symmetric monoidal category. We thus obtain a categorical analogue of the classical localization of a ring with respect to a multiplicative subset....

Finding H -partitions efficiently

Simone Dantas, Celina M. H. de Figueiredo, Sylvain Gravier, Sulamita Klein (2005)

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

We study the concept of an H -partition of the vertex set of a graph G , which includes all vertex partitioning problems into four parts which we require to be nonempty with only external constraints according to the structure of a model graph H , with the exception of two cases, one that has already been classified as polynomial, and the other one remains unclassified. In the context of more general vertex-partition problems, the problems addressed in this paper have these properties: non-list, 4 -part,...

Currently displaying 1 – 20 of 78

Page 1 Next