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 solidity of general varieties of tree languages
For a class of hypersubstitutions 𝓚, we define the 𝓚-solidity of general varieties of tree languages (GVTLs) that contain tree languages over all alphabets, general varieties of finite algebras (GVFAs), and general varieties of finite congruences (GVFCs). We show that if 𝓚 is a so-called category of substitutions, a GVTL is 𝓚-solid exactly in case the corresponding GVFA, or the corresponding GVFC, is 𝓚-solid. We establish the solidity status of several known GVTLs with respect to certain categories...
On the solution of optimal performance of page storage hierarchies with an independent reference string
On the stack-size of general tries
Digital trees or tries are a general purpose flexible data structure that implements dictionaries built on words. The present paper is focussed on the average-case analysis of an important parameter of this tree-structure, i.e., the stack-size. The stack-size of a tree is the memory needed by a storage-optimal preorder traversal. The analysis is carried out under a general model in which words are produced by a source (in the information-theoretic sense) that emits symbols. Under some natural assumptions...
On the Stack-Size of General Tries
Digital trees or tries are a general purpose flexible data structure that implements dictionaries built on words. The present paper is focussed on the average-case analysis of an important parameter of this tree-structure, i.e., the stack-size. The stack-size of a tree is the memory needed by a storage-optimal preorder traversal. The analysis is carried out under a general model in which words are produced by a source (in the information-theoretic sense) that emits symbols. Under some natural...
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 structure of Valiant's complexity class.
On the structure of (−β)-integers
The (−β)-integers are natural generalisations of the β-integers, and thus of the integers, for negative real bases. When β is the analogue of a Parry number, we describe the structure of the set of (−β)-integers by a fixed point of an anti-morphism.
On the Symbolic Evaluation of Determinants
On the syntactic complexity of parallel communicating grammar systems
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 Threshold of Bounded Pseudo-Distances.
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].