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...
On the size of the subword complexity of square-free DOL languages.
On the size of transducers for bidirectional decoding of prefix codes
In a previous paper [L. Giambruno and S. Mantaci, Theoret. Comput. Sci. 411 (2010) 1785–1792] a bideterministic transducer is defined for the bidirectional deciphering of words by the method introduced by Girod [IEEE Commun. Lett. 3 (1999) 245–247]. Such a method is defined using prefix codes. Moreover a coding method, inspired by the Girod’s one, is introduced, and a transducer that allows both right-to-left and left-to-right decoding by this method is defined. It is proved also that this transducer...
On the size of transducers for bidirectional decoding of prefix codes
In a previous paper [L. Giambruno and S. Mantaci, Theoret. Comput. Sci. 411 (2010) 1785–1792] a bideterministic transducer is defined for the bidirectional deciphering of words by the method introduced by Girod [IEEE Commun. Lett. 3 (1999) 245–247]. Such a method is defined using prefix codes. Moreover a coding method, inspired by the Girod’s one, is introduced, and a transducer that allows both right-to-left and left-to-right decoding by this...
On the size of transducers for bidirectional decoding of prefix codes
In a previous paper [L. Giambruno and S. Mantaci, Theoret. Comput. Sci. 411 (2010) 1785–1792] a bideterministic transducer is defined for the bidirectional deciphering of words by the method introduced by Girod [IEEE Commun. Lett. 3 (1999) 245–247]. Such a method is defined using prefix codes. Moreover a coding method, inspired by the Girod’s one, is introduced, and a transducer that allows both right-to-left and left-to-right decoding by this...
On the skeletal structure of Pascal statement
On the state complexity of semi-quantum finite automata
Some of the most interesting and important results concerning quantum finite automata are those showing that they can recognize certain languages with (much) less resources than corresponding classical finite automata. This paper shows three results of such a type that are stronger in some sense than other ones because (a) they deal with models of quantum finite automata with very little quantumness (so-called semi-quantum one- and two-way finite automata); (b) differences, even comparing with probabilistic...
On the structure of general stochastic automata
On the structure of recognizable languages of dependence graphs
On the syntactic complexity of tree series
We display a complexity notion based on the syntax of a tree series which yields two distinct hierarchies, one within the class of recognizable tree series and another one in the class of non-recognizable tree series.
On the topological complexity of infinitary rational relations
We prove in this paper that there exists some infinitary rational relations which are analytic but non Borel sets, giving an answer to a question of Simonnet [20].
On the Topological Complexity of Infinitary Rational Relations
We prove in this paper that there exists some infinitary rational relations which are analytic but non Borel sets, giving an answer to a question of Simonnet [20].
On two problems of mice