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 2 Next

Displaying 21 – 40 of 67

Showing per page

The number of binary rotation words

A. Frid, D. Jamet (2014)

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

We consider binary rotation words generated by partitions of the unit circle to two intervals and give a precise formula for the number of such words of length n. We also give the precise asymptotics for it, which happens to be Θ(n4). The result continues the line initiated by the formula for the number of all Sturmian words obtained by Lipatov [Problemy Kibernet. 39 (1982) 67–84], then independently by Mignosi [Theoret. Comput. Sci. 82 (1991) 71–84], and others.

The sum-product algorithm: algebraic independence and computational aspects

Francesco M. Malvestuto (2013)

Kybernetika

The sum-product algorithm is a well-known procedure for marginalizing an “acyclic” product function whose range is the ground set of a commutative semiring. The algorithm is general enough to include as special cases several classical algorithms developed in information theory and probability theory. We present four results. First, using the sum-product algorithm we show that the variable sets involved in an acyclic factorization satisfy a relation that is a natural generalization of probability-theoretic...

The theorem of Fine and Wilf for relational periods

Vesa Halava, Tero Harju, Tomi Kärki (2009)

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

We consider relational periods, where the relation is a compatibility relation on words induced by a relation on letters. We prove a variant of the theorem of Fine and Wilf for a (pure) period and a relational period.

The theorem of Fine and Wilf for relational periods

Vesa Halava, Tero Harju, Tomi Kärki (2008)

RAIRO - Theoretical Informatics and Applications

We consider relational periods, where the relation is a compatibility relation on words induced by a relation on letters. We prove a variant of the theorem of Fine and Wilf for a (pure) period and a relational period.

The Uniform Minimum-Ones 2SAT Problem and its Application to Haplotype Classification

Hans-Joachim Böckenhauer, Michal Forišek, Ján Oravec, Björn Steffen, Kathleen Steinhöfel, Monika Steinová (2010)

RAIRO - Theoretical Informatics and Applications

Analyzing genomic data for finding those gene variations which are responsible for hereditary diseases is one of the great challenges in modern bioinformatics. In many living beings (including the human), every gene is present in two copies, inherited from the two parents, the so-called haplotypes. In this paper, we propose a simple combinatorial model for classifying the set of haplotypes in a population according to their responsibility for a certain genetic disease. This model is based...

Currently displaying 21 – 40 of 67