Calculs approchés de la borne inférieure de valeurs réparties
Characteristic formulae for timed automata
Characteristic Formulae for Timed Automata
This paper offers characteristic formula constructions in the real-time logic Lν for several behavioural relations between (states of) timed automata. The behavioural relations studied in this work are timed (bi)similarity, timed ready simulation, faster-than bisimilarity and timed trace inclusion. The characteristic formulae delivered by our constructions have size which is linear in that of the timed automaton they logically describe. This also applies to the characteristic formula for...
Characterizing the complexity of boolean functions represented by well-structured graph-driven parity-FBDDs
We investigate well-structured graph-driven parity-FBDDs, which strictly generalize the two well-known models parity OBDDs and well-structured graph-driven FBDDs. The first main result is a characterization of the complexity of Boolean functions represented by well-structured graph-driven parity-FBDDs in terms of invariants of the function represented and the graph-ordering used. As a consequence, we derive a lower bound criterion and prove an exponential lower bound for certain linear code functions....
Characterizing the Complexity of Boolean Functions represented by Well-Structured Graph-Driven Parity-FBDDs
We investigate well-structured graph-driven parity-FBDDs, which strictly generalize the two well-known models parity OBDDs and well-structured graph-driven FBDDs. The first main result is a characterization of the complexity of Boolean functions represented by well-structured graph-driven parity-FBDDs in terms of invariants of the function represented and the graph-ordering used. As a consequence, we derive a lower bound criterion and prove an exponential lower bound for certain linear code functions. The...
Circuit lower bounds and linear codes.
Complexity classes for membrane systems
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
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...
Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs
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...
Construction of parallel programs with networks of cooperating processes
Convergence behavior of the (1 +, λ) evolution strategy on the ridge functions.
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?
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.