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

Displaying 21 – 40 of 126

Showing per page

Circular splicing and regularity

Paola Bonizzoni, Clelia De Felice, Giancarlo Mauri, Rosalba Zizza (2010)

RAIRO - Theoretical Informatics and Applications

Circular splicing has been very recently introduced to model a specific recombinant behaviour of circular DNA, continuing the investigation initiated with linear splicing. In this paper we restrict our study to the relationship between regular circular languages and languages generated by finite circular splicing systems and provide some results towards a characterization of the intersection between these two classes. We consider the class of languages X*, called here star languages, which are closed...

Complexity classes for membrane systems

Antonio E. Porreca, Giancarlo Mauri, Claudio Zandron (2006)

RAIRO - Theoretical Informatics and Applications

We compare various computational complexity classes defined within the framework of membrane systems, a distributed parallel computing device which is inspired from the functioning of the cell, with usual computational complexity classes for Turing machines. In particular, we focus our attention on the comparison among complexity classes for membrane systems with active membranes (where new membranes can be created by division of existing membranes) and the classes PSPACE, EXP, and EXPSPACE.

Complexity theoretical results on nondeterministic graph-driven read-once branching programs

Beate Bollig (2003)

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

Branching programs are a well-established computation model for boolean functions, especially read-once branching programs (BP1s) have been studied intensively. Recently two restricted nondeterministic (parity) BP1 models, called nondeterministic (parity) graph-driven BP1s and well-structured nondeterministic (parity) graph-driven BP1s, have been investigated. The consistency test for a BP-model M is the test whether a given BP is really a BP of model M . Here it is proved that the consistency test...

Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs

Beate Bollig (2010)

RAIRO - Theoretical Informatics and Applications

Branching programs are a well-established computation model for boolean functions, especially read-once branching programs (BP1s) have been studied intensively. Recently two restricted nondeterministic (parity) BP1 models, called nondeterministic (parity) graph-driven BP1s and well-structured nondeterministic (parity) graph-driven BP1s, have been investigated. The consistency test for a BP-model M is the test whether a given BP is really a BP of model M. Here it is proved that the consistency...

Division in logspace-uniform NC 1

Andrew Chiu, George Davida, Bruce Litow (2001)

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

Beame, Cook and Hoover were the first to exhibit a log-depth, polynomial size circuit family for integer division. However, the family was not logspace-uniform. In this paper we describe log-depth, polynomial size, logspace-uniform, i.e., NC 1 circuit family for integer division. In particular, by a well-known result this shows that division is in logspace. We also refine the method of the paper to show that division is in dlogtime-uniform NC 1 .

Division in logspace-uniform NC1

Andrew Chiu, George Davida, Bruce Litow (2010)

RAIRO - Theoretical Informatics and Applications

Beame, Cook and Hoover were the first to exhibit a log-depth, polynomial size circuit family for integer division. However, the family was not logspace-uniform. In this paper we describe log-depth, polynomial size, logspace-uniform, i.e., NC1 circuit family for integer division. In particular, by a well-known result this shows that division is in logspace. We also refine the method of the paper to show that division is in dlogtime-uniform NC1.

Domain-Free λµ-Calculus

Ken-Etsu Fujita (2010)

RAIRO - Theoretical Informatics and Applications

We introduce a domain-free λµ-calculus of call-by-value as a short-hand for the second order Church-style. Our motivation comes from the observation that in Curry-style polymorphic calculi, control operators such as callcc-operators cannot, in general, handle correctly the terms placed on the control operator's left, so that the Curry-style system can fail to prove the subject reduction property. Following the continuation semantics, we also discuss the notion of values in classical system,...

Efficient simulation of synchronous systems by multi-speed systems

Tomasz Jurdziński, Mirosław Kutyłowski, Jan Zatopiański (2005)

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

We consider systems consisting of finite automata communicating by exchanging messages and working on the same read-only data. We investigate the situation in which the automata work with constant but different speeds. We assume furthermore that the automata are not aware of the speeds and they cannot measure them directly. Nevertheless, the automata have to compute a correct output. We call this model multi-speed systems of finite automata. Complexity measure that we consider here is the number...

Efficient simulation of synchronous systems by multi-speed systems

Tomasz Jurdziński, Mirosław Kutyłowski, Jan Zatopiański (2010)

RAIRO - Theoretical Informatics and Applications

We consider systems consisting of finite automata communicating by exchanging messages and working on the same read-only data. We investigate the situation in which the automata work with constant but different speeds. We assume furthermore that the automata are not aware of the speeds and they cannot measure them directly. Nevertheless, the automata have to compute a correct output. We call this model multi-speed systems of finite automata. Complexity measure that we consider here is the...

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...

Generating Networks of Splicing Processors

Jürgen Dassow, Florin Manea, Bianca Truthe (2012)

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

In this paper, we introduce generating networks of splicing processors (GNSP for short), a formal languages generating model related to networks of evolutionary processors and to accepting networks of splicing processors. We show that all recursively enumerable languages can be generated by GNSPs with only nine processors. We also show, by direct simulation, that two other variants of this computing model, where the communication between processors is conducted in different ways, have the same computational...

Generating Networks of Splicing Processors

Jürgen Dassow, Florin Manea, Bianca Truthe (2012)

RAIRO - Theoretical Informatics and Applications

In this paper, we introduce generating networks of splicing processors (GNSP for short), a formal languages generating model related to networks of evolutionary processors and to accepting networks of splicing processors. We show that all recursively enumerable languages can be generated by GNSPs with only nine processors. We also show, by direct simulation, that two other variants of this computing model, where the communication between processors...

Currently displaying 21 – 40 of 126