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 88

Showing per page

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

Convergence behavior of the (1 +, λ) evolution strategy on the ridge functions.

Ahmet Irfan Oyman, Hans-Georg Beyer, Hans-Paul Schwefel (2000)

Mathware and Soft Computing

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

Could a combinatorial optimization problem be solved by a differential equation?

Pedro Martínez Talaván, Javier Yáñez (2001)

RACSAM

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.

Different time solutions for the firing squad synchronization problem on basic grid networks

Jozef Gruska, Salvatore La Torre, Margherita Napoli, Mimmo Parente (2006)

RAIRO - Theoretical Informatics and Applications

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

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.

Fuzzy systems and neural networks XML schemas for Soft Computing.

Adolfo Rodríguez de Soto, Conrado Andreu Capdevila, E. C. Fernández (2003)

Mathware and Soft Computing

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

Hierarchies of weakly monotone restarting automata

František Mráz, Friedrich Otto (2005)

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

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.

Hierarchies of weakly monotone restarting automata

František Mráz, Friedrich Otto (2010)

RAIRO - Theoretical Informatics and Applications

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.

Immunity and Simplicity for Exact Counting and Other Counting Classes

J. Rothe (2010)

RAIRO - Theoretical Informatics and Applications

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, C = P , and ⊕P in all possible pairwise combinations. Our main result is that there is an oracle A relative to which C = P contains a set that is immune BPP⊕P. In particular, this C = P A set is immune to PHA and to ⊕PA. Strengthening...

Lower bounds for Las Vegas automata by information theory

Mika Hirvensalo, Sebastian Seibert (2003)

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

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 ≥ n p , 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...

Lower Bounds for Las Vegas Automata by Information Theory

Mika Hirvensalo, Sebastian Seibert (2010)

RAIRO - Theoretical Informatics and Applications

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

Measuring the problem-relevant information in input

Stefan Dobrev, Rastislav Královič, Dana Pardubská (2009)

RAIRO - Theoretical Informatics and Applications

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