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
A space lower bound for acceptance by one-way -alternating machines
A Space Lower Bound for Acceptance by One-Way Π2-Alternating Machines
We show that one-way Π2-alternating Turing machines cannot accept unary nonregular languages in o(log n) space. This holds for an accept mode of space complexity measure, defined as the worst cost of any accepting computation. This lower bound should be compared with the corresponding bound for one-way Σ2-alternating machines, that are able to accept unary nonregular languages in space O(log log n). Thus, Σ2-alternation is more powerful than Π2-alternation for space bounded one-way machines with...
A special form of grammars
A stochastic approach to robot plan formation