On the directability of automata
On the Ehrenfeucht conjecture for DOL languages
On the equality sets for homomorphisms on free monoids with two generators
On the equivalence of compositions of morphisms and inverse morphisms on regular languages
On the expressive power of the shuffle operator matched with intersection by regular sets
We investigate the complexity of languages described by some expressions containing shuffle operator and intersection. We show that deciding whether the shuffle of two words has a nonempty intersection with a regular set (or fulfills some regular pattern) is NL-complete. Furthermore we show that the class of languages of the form , with a shuffle language and a regular language , contains non-semilinear languages and does not form a family of mildly context- sensitive languages.
On the expressive power of the shuffle operator matched with intersection by regular sets
We investigate the complexity of languages described by some expressions containing shuffle operator and intersection. We show that deciding whether the shuffle of two words has a nonempty intersection with a regular set (or fulfills some regular pattern) is NL-complete. Furthermore we show that the class of languages of the form , with a shuffle language L and a regular language R, contains non-semilinear languages and does not form a family of mildly context- sensitive languages.
On the generative capacity of colonies
On the geometry of computations
On the greatest congruence relation contained in an equivalence relation and its applications to the algebraic theory of machines
On the hierarchy of Petri net languages
On the influence of the state encoding on OBDD-representations of finite state machines
On the Influence of the State Encoding on OBDD-Representations of Finite State Machines
Ordered binary decision diagrams are an important data structure for the representation of Boolean functions. Typically, the underlying variable ordering is used as an optimization parameter. When finite state machines are represented by OBDDs the state encoding can be used as an additional optimization parameter. In this paper, we analyze the influence of the state encoding on the OBDD-representations of counter-type finite state machines. In particular, we prove lower bounds, derive exact...
On the invertibility of finite linear transducers
Linear finite transducers underlie a series of schemes for Public Key Cryptography (PKC) proposed in the 90s of the last century. The uninspiring and arid language then used, condemned these works to oblivion. Although some of these schemes were afterwards shown to be insecure, the promise of a new system of PKC relying on different complexity assumptions is still quite exciting. The algorithms there used depend heavily on the results of invertibility of linear transducers. In this paper we introduce...
On the k-reversibility of finite automata.
On the membership problem for pseudo-varieties of commutative semigroups.
On the minimum error in addition processes of positive floating-point numbers
On the number of initial segments of a finite set of sequences (finite language)
On the periodicity of morphisms on free monoids
On the product of all elements in a finite group.
On the property of probabilistic context-free grammars.