A Complexity Calculus for Recursive Tree Algorithms
A compositional approach to synchronize two dimensional networks of processors
A Compositional Approach to Synchronize Two Dimensional Networks of Processors
The problem of synchronizing a network of identical processors that work synchronously at discrete steps is studied. Processors are arranged as an array of m rows and n columns and can exchange each other only one bit of information. We give algorithms which synchronize square arrays of (n × n) processors and give some general constructions to synchronize arrays of (m × n) processors. Algorithms are given to synchronize in time n2, , and 2n a square array of (n × n) processors. Our approach...
A concurrency control problem in a time-sharing system with different job types
A conjecture on the concatenation product
In a previous paper, the authors studied the polynomial closure of a variety of languages and gave an algebraic counterpart, in terms of Mal’cev products, of this operation. They also formulated a conjecture about the algebraic counterpart of the boolean closure of the polynomial closure – this operation corresponds to passing to the upper level in any concatenation hierarchy. Although this conjecture is probably true in some particular cases, we give a counterexample in the general case. Another...
A conjecture on the concatenation product
In a previous paper, the authors studied the polynomial closure of a variety of languages and gave an algebraic counterpart, in terms of Mal'cev products, of this operation. They also formulated a conjecture about the algebraic counterpart of the boolean closure of the polynomial closure – this operation corresponds to passing to the upper level in any concatenation hierarchy. Although this conjecture is probably true in some particular cases, we give a counterexample in the general case....
A connection between Computer Science and Fuzzy Theory: Midpoints and running time of computing.
A continuous family of automata : the Ising automata
A contribution to the top-to-bottom recognizer rehabilitation
A convenient category for directed homotopy.
A criterion for non-automaticity of sequences.
A decision method for the recognizability of sets defined by number systems
A deductive calculus for conditional equational systems with built-in predicates as premises.
A deterministic subclass of context-free languages
A Divide and Conquer Method for the Symmetric Tridiagonal Eigenproblem.
A factor graph based genetic algorithm
We propose a new linkage learning genetic algorithm called the Factor Graph based Genetic Algorithm (FGGA). In the FGGA, a factor graph is used to encode the underlying dependencies between variables of the problem. In order to learn the factor graph from a population of potential solutions, a symmetric non-negative matrix factorization is employed to factorize the matrix of pair-wise dependencies. To show the performance of the FGGA, encouraging experimental results on different separable problems...
A fast algorithm to decide on the equivalence of stateless DPDA
A Fast Las Vegas Algorithm for Triangulating a Simple Polygon.
A finite axiomatization of nondeterministic regular expressions
A Finite Axiomatization of Nondeterministic Regular Expressions
An alternative (tree-based) semantics for a class of regular expressions is proposed that assigns a central rôle to the + operator and thus to nondeterminism and nondeterministic choice. For the new semantics a consistent and complete axiomatization is obtained from the original axiomatization of regular expressions by Salomaa and by Kozen by dropping the idempotence law for + and the distribution law of • over +.