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.
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.
The search session has expired. Please query the service again.
Displaying 21 –
40 of
126
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...
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.
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 is the test whether a given BP is really a BP of model . Here it is proved that the consistency test...
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...
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., 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 .
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.
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,...
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...
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...
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...
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...
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