The search session has expired. Please query the service again.
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...
The convergence behavior of (1 +, λ)-ES is investigated at parabolic ridge, sharp ridge, and at the general case of the ridge functions. The progress rate, the distance to the ridge axis, the success rate, and the success probability are used in the analysis. The strong dependency of the (1 + λ)-ES to the initial conditions is shown using parabolic ridge test function when low distances to the ridge axis are chosen as the start value. The progress rate curve and the success probability curve of...
El Problema del Viajante puede plantearse a partir del modelo de red neuronal continuo de Hopfield, que determina una solución de equilibrio para una ecuación diferencial con parámetros desconocidos. En el artículo se detalla el procedimiento de determinación de dichos parámetros con el fin de asegurar que la solución de la ecuación diferencial proporcione soluciones válidas para el Problema del Viajante.
We present several solutions to
the Firing Squad Synchronization Problem on grid networks of
different shapes.
The nodes are finite state processors that
work in unison with other processors and in synchronized discrete steps. The
networks we deal with are: the line, the ring and the square.
For all of these models we consider one- and two-way
communication modes and we also constrain the quantity of information
that adjacent processors can exchange at each step.
We first present synchronization...
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.
This article presents an XML[2] based language for the specification of objects in the Soft Computing area. The design promotes reuse and takes a compositional approach in which more complex constructs are built from simpler ones; it is also independent of implementation details as the definition of the language only states the expected behaviour of every possible implementation. Here the basic structures for the specification of concepts in the Fuzzy Logic area are described and a simple construct...
It is known that the weakly monotone restarting automata accept exactly the growing context-sensitive languages. We introduce a measure on the degree of weak monotonicity and show that the language classes obtained in this way form strict hierarchies for the various types of deterministic and nondeterministic restarting automata without auxiliary symbols.
It is known that the weakly monotone restarting automata accept
exactly the growing context-sensitive languages. We introduce a
measure on the degree of weak monotonicity and show that the
language classes obtained in this way form strict hierarchies for
the various types of deterministic and nondeterministic restarting
automata without auxiliary symbols.
Ko [26] and Bruschi [11] independently showed that, in
some relativized world, PSPACE (in fact, ⊕P) contains a set
that is immune to the polynomial hierarchy (PH). In this paper, we
study and settle the question of relativized separations with
immunity for PH and the counting classes PP, , and ⊕P
in all possible pairwise combinations. Our main result is that there
is an oracle A relative to which contains a set that is immune BPP⊕P.
In particular, this set is immune to PHA and to ⊕PA. Strengthening...
We show that the size of a Las Vegas automaton and the size of a complete, minimal deterministic automaton accepting a regular language are polynomially related. More precisely, we show that if a regular language is accepted by a Las Vegas automaton having states such that the probability for a definite answer to occur is at least , then , where is the number of the states of the minimal deterministic automaton accepting . Earlier this result has been obtained in [2] by using a reduction...
We show that the size of a Las Vegas automaton
and the size of a complete, minimal deterministic
automaton accepting a regular
language are polynomially related. More precisely, we show
that if a regular language L is accepted by a
Las Vegas automaton having r states such that
the probability for a definite answer to occur is at least p,
then r ≥ np, where n is the number of the states
of the minimal deterministic automaton accepting L.
Earlier this result has been obtained
in [2] by using a reduction...
We propose a new way of characterizing the complexity of online problems.
Instead of measuring the degradation of the output quality caused by the ignorance
of the future we choose to quantify the amount of additional global information
needed for an online algorithm to solve the problem optimally. In our model, the
algorithm cooperates with an oracle that can see the whole input. We define
the advice complexity of the problem to be the minimal number of bits
(normalized per input request, and...
Currently displaying 21 –
40 of
88