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.
On the recognizability of self-generating sets.
On the role of configurations in the theory of grammars
On the semidirect product of the pseudovariety of semilattices by a locally finite pseudovariety of groups
On the separating power of EOL systems
On the size of context-free grammars
On the size of DeRemer's analyzers
On the size of one-way quantum finite automata with periodic behaviors
We show that, for any stochastic event of period , there exists a measure-once one-way quantum finite automaton (1qfa) with at most states inducing the event , for constants , , satisfying . This fact is proved by designing an algorithm which constructs the desired 1qfa in polynomial time. As a consequence, we get that any periodic language of period can be accepted with isolated cut point by a 1qfa with no more than states. Our results give added evidence of the strength of measure-once...
On the Size of One-way Quantum Finite Automata with Periodic Behaviors
We show that, for any stochastic event p of period n, there exists a measure-once one-way quantum finite automaton (1qfa) with at most states inducing the event ap+b, for constants a>0, b ≥ 0, satisfying a+b ≥ 1. This fact is proved by designing an algorithm which constructs the desired 1qfa in polynomial time. As a consequence, we get that any periodic language of period n can be accepted with isolated cut point by a 1qfa with no more than states. Our results give added evidence of the...