A Polynomial Solution for the Potato-peeling Problem.
A Polynomial-Time Linear Decision Tree for the Traveling Salesman Problem and Other NP-Complete Problems.
A probabilistic analysis of a new satisfiability algorithm
A probabilistic approach to automaton-environment systems
A property of biprefix codes
A property of the Schützenberger product.
À propos de la sémantique de l'appel par valeur selon A. Arnold
A reformulation of matrix graph grammars with Boolean complexes.
A remark on morphic sturmian words
A selection property of the boolean -calculus and some of its applications
A selection-based formal description of an environment
A semantic construction of two-ary integers
To binary trees, two-ary integers are what usual integers are to natural numbers, seen as unary trees. We can represent two-ary integers as binary trees too, yet with leaves labelled by binary words and with a structural restriction. In a sense, they are simpler than the binary trees, they relativize. Hence, contrary to the extensions known from Arithmetic and Algebra, this integer extension does not make the starting objects more complex. We use a semantic construction to get this extension. This...
A semigroup characterization of dot-depth one languages
A sharpening of the Parikh mapping
In this paper we introduce a sharpening of the Parikh mapping and investigate its basic properties. The new mapping is based on square matrices of a certain form. The classical Parikh vector appears in such a matrix as the second diagonal. However, the matrix product gives more information about a word than the Parikh vector. We characterize the matrix products and establish also an interesting interconnection between mirror images of words and inverses of matrices.
A sharpening of the Parikh mapping
In this paper we introduce a sharpening of the Parikh mapping and investigate its basic properties. The new mapping is based on square matrices of a certain form. The classical Parikh vector appears in such a matrix as the second diagonal. However, the matrix product gives more information about a word than the Parikh vector. We characterize the matrix products and establish also an interesting interconnection between mirror images of words and inverses of .
A Simple and Relatively Efficient Triangulation of the n-Cube.
A simple proof of Valiant's lemma
A simplification functor for coalgebras.
A Six States Minimal Time Solution to the Firing Squad Synchronization Problem
A solvable case of the set-partitioning problem