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.
An application of the Ehrenfeucht-Fraisse game in formal language theory
An application of the theory of intuitionistic fuzzy multigraphs.
In a recent paper by one of the authors it has been shown that there is a relationship between algebraic structures and labeled transition systems. Indeed, it has been shown that an algebraic structures can be viewed as labeled transition systems, which can also be viewed as multigraphs. In this paper, we extend this work by providing an estimation of the transition possibilities between vertices that are connected with multiarcs.
An approach to parallel algorithm design
An automata-theoretic approach to the study of the intersection of two submonoids of a free monoid
We investigate the intersection of two finitely generated submonoids of the free monoid on a finite alphabet. To this purpose, we consider automata that recognize such submonoids and we study the product automata recognizing their intersection. By using automata methods we obtain a new proof of a result of Karhumäki on the characterization of the intersection of two submonoids of rank two, in the case of prefix (or suffix) generators. In a more general setting, for an arbitrary number of generators,...