Algorithms for weighted graph problems on the modified cellular graph automaton
Almost Tight Bounds for e-Nets.
Almost Tight Upper Bounds for Lower Envelopes in Higher Dimensions.
Amenable groups and cellular automata
We show that the theorems of Moore and Myhill hold for cellular automata whose universes are Cayley graphs of amenable finitely generated groups. This extends the analogous result of A. Machi and F. Mignosi “Garden of Eden configurations for cellular automata on Cayley graphs of groups” for groups of sub-exponential growth.
An worst case bounded special knapsack with two constraints
An abstract monadic semantics for value recursion
This paper proposes an operational semantics for value recursion in the context of monadic metalanguages. Our technique for combining value recursion with computational effects works uniformly for all monads. The operational nature of our approach is related to the implementation of recursion in Scheme and its monadic version proposed by Friedman and Sabry, but it defines a different semantics and does not rely on assignments. When contrasted to the axiomatic approach proposed by Erkök and Launchbury,...
An abstract monadic semantics for value recursion
This paper proposes an operational semantics for value recursion in the context of monadic metalanguages. Our technique for combining value recursion with computational effects works uniformly for all monads. The operational nature of our approach is related to the implementation of recursion in Scheme and its monadic version proposed by Friedman and Sabry, but it defines a different semantics and does not rely on assignments. When contrasted to the axiomatic approach proposed by Erkök and Launchbury,...
An algebraic treatment of flow diagrams and its application to generalized recursion theory
An algorithm for finding a minimal recursive path ordering
An algorithm for reduction of complexity of relations in a system of variables
Let us have a system of variables, among which there are complicated dependences. Assuming reflexivity and transitivity of the relation " depends on ", a simple algorithm is proposed which produces all dependences in an optimized way, without losing information.
An algorithm for the solution of fixed-point equations for infinite words
An algorithm to calculate the kernel of certain polynomial ring homomorphisms.
An almost naive algorithm for finding relative neighbourhood graphs in metrics
An alternative formulation of the factorization conjecture for codes. (Une formulation alternative de la conjecture de factorisation des codes.)
An analysis of Lambek's production machines
An answer to a question by J. Milnor.
An aperiodicity problem for multiwords
Multiwords are words in which a single symbol can be replaced by a nonempty set of symbols. They extend the notion of partial words. A word w is certain in a multiword M if it occurs in every word that can be obtained by selecting one single symbol among the symbols provided in each position of M. Motivated by a problem on incomplete databases, we investigate a variant of the pattern matching problem which is to decide whether a word w is certain in a multiword M. We study the language CERTAIN(w)...
An aperiodicity problem for multiwords
Multiwords are words in which a single symbol can be replaced by a nonempty set of symbols. They extend the notion of partial words. A word w is certain in a multiword M if it occurs in every word that can be obtained by selecting one single symbol among the symbols provided in each position of M. Motivated by a problem on incomplete databases, we investigate a variant of the pattern matching problem which is to decide whether a word w is certain in a multiword M. We study the language CERTAIN(w)...
An application of logical-probabilistic expressions to the realization of stochastic automata
An application of results by Hardy, Ramanujan and Karamata to Ackermannian functions.