All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 14 Next

Displaying 261 – 280 of 305

Showing per page

On the size of transducers for bidirectional decoding of prefix codes

Laura Giambruno, Sabrina Mantaci (2012)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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

Laura Giambruno, Sabrina Mantaci (2012)

RAIRO - Theoretical Informatics and Applications

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

Laura Giambruno, Sabrina Mantaci (2012)

RAIRO - Theoretical Informatics and Applications

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 solidity of general varieties of tree languages

Magnus Steinby (2012)

Discussiones Mathematicae - General Algebra and Applications

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 state complexity of semi-quantum finite automata

Shenggen Zheng, Jozef Gruska, Daowen Qiu (2014)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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 syntactic complexity of tree series

Symeon Bozapalidis, Antonios Kalampakas (2010)

RAIRO - Theoretical Informatics and Applications

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

Olivier Finkel (2003)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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 weak pigeonhole principle

Jan Krajíček (2001)

Fundamenta Mathematicae

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...

On the weighted Euclidean matching problem in ℝ d

Birgit Anthes, Ludger Rüschendorf (2001)

Applicationes Mathematicae

A partitioning algorithm for the Euclidean matching problem in ℝ d 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 n ( l o g n ) p - 1 and approximates the optimal matching in the probabilistic sense.

On time-varying networks of time-varying semiautomata

Louise Martin, Dan A. Simovici (1983)

Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti Lincei. Matematica e Applicazioni

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.

On Varieties of Literally Idempotent Languages

Ondřej Klíma, Libor Polák (2008)

RAIRO - Theoretical Informatics and Applications

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