The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
Displaying 261 –
280 of
305
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...
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...
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...
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...
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...
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.
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].
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].
We investigate the proof complexity, in (extensions of) resolution and in bounded arithmetic, of the weak pigeonhole principle and of the Ramsey theorem. In particular, we link the proof complexities of these two principles. Further we give lower bounds to the width of resolution proofs and to the size of (extensions of) tree-like resolution proofs of the Ramsey theorem.
We establish a connection between provability of WPHP in fragments of bounded arithmetic and cryptographic assumptions (the existence...
A partitioning algorithm for the Euclidean matching problem in is introduced and analyzed in a probabilistic model. The algorithm uses elements from the fixed dissection algorithm of Karp and Steele (1985) and the Zig-Zag algorithm of Halton and Terada (1982) for the traveling salesman problem. The algorithm runs in expected time and approximates the optimal matching in the probabilistic sense.
Si utilizza la nozione di réte di semiautòmi con struttura variabile nel tempo, per ottenere un criterio di decomposizione dei semiautòmi con struttura variabile. Si mette in evidenza il ruolo di una congruenza nella decomposizione di questo tipo di semiautònomi.
A language L ⊆A* is literally idempotent in case that
ua2v ∈ L if and only if uav ∈ L, for each u,v ∈ A*, a ∈ A.
Varieties of literally idempotent languages result naturally by taking
all literally idempotent languages in a classical (positive) variety
or by considering a certain closure operator on classes of languages.
We initiate the systematic study of such varieties. Various classes of
literally idempotent languages can
be characterized using syntactic methods.
A starting example is the...
Currently displaying 261 –
280 of
305