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
Addition molle et fonctions p-locales.
Affine Parikh automata∗
The Parikh finite word automaton (PA) was introduced and studied in 2003 by Klaedtke and Rueß. Natural variants of the PA arise from viewing a PA equivalently as an automaton that keeps a count of its transitions and semilinearly constrains their numbers. Here we adopt this view and define the affine PA, that extends the PA by having each transition induce an affine transformation on the PA registers, and the PA on letters, that restricts the PA...
Affine Parikh automata
The Parikh finite word automaton (PA) was introduced and studied in 2003 by Klaedtke and Rueß. Natural variants of the PA arise from viewing a PA equivalently as an automaton that keeps a count of its transitions and semilinearly constrains their numbers. Here we adopt this view and define the affine PA, that extends the PA by having each transition induce an affine transformation on the PA registers, and the PA on letters, that restricts the PA by forcing any two transitions on the same letter...