A property of biprefix codes
A property of the Schützenberger product.
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 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 proof of Valiant's lemma
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
A theorem on binary relations and infinite languages.
A theory of complexity of monadic recursion schemes
A unified approach to control problems in discrete event processes
A unified Framework to compute over tree synchronized grammars and primal grammars.
Abgeschwächte Observabilitätsbegriffe für stochastische Automaten
Abstract numeration systems on bounded languages and multiplication by a constant.
Acceptors and generalized -grammars