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

Displaying 81 – 100 of 133

Showing per page

Abelian periods, partial words, and an extension of a theorem of Fine and Wilf

Francine Blanchet-Sadri, Sean Simmons, Amelia Tebbe, Amy Veprauskas (2013)

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

Recently, Constantinescu and Ilie proved a variant of the well-known periodicity theorem of Fine and Wilf in the case of two relatively prime abelian periods and conjectured a result for the case of two non-relatively prime abelian periods. In this paper, we answer some open problems they suggested. We show that their conjecture is false but we give bounds, that depend on the two abelian periods, such that the conjecture is true for all words having length at least those bounds and show that some...

Algebraic and graph-theoretic properties of infinite n -posets

Zoltán Ésik, Zoltán L. Németh (2005)

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

A Σ -labeled n -poset is an (at most) countable set, labeled in the set Σ , equipped with n partial orders. The collection of all Σ -labeled n -posets is naturally equipped with n binary product operations and n ω -ary product operations. Moreover, the ω -ary product operations give rise to n ...

Algebraic and graph-theoretic properties of infinite n-posets

Zoltán Ésik, Zoltán L. Németh (2010)

RAIRO - Theoretical Informatics and Applications

A Σ-labeled n-poset is an (at most) countable set, labeled in the set Σ, equipped with n partial orders. The collection of all Σ-labeled n-posets is naturally equipped with n binary product operations and nω-ary product operations. Moreover, the ω-ary product operations give rise to nω-power operations. We show that those Σ-labeled n-posets that can be generated from the singletons by the binary and ω-ary product operations form the free algebra on Σ in a variety axiomatizable by an infinite collection...

Algorithms for Finding Unitals and Maximal Arcs in Projective Planes of Order 16

Stoichev, Stoicho (2007)

Serdica Journal of Computing

The paper has been presented at the International Conference Pioneers of Bulgarian Mathematics, Dedicated to Nikola Obreshkoff and Lubomir Tschakalo ff , Sofia, July, 2006.Two heuristic algorithms (M65 and M52) for finding respectively unitals and maximal arcs in projective planes of order 16 are described. The exact algorithms based on exhaustive search are impractical because of the combinatorial explosion (huge number of combinations to be checked). Algorithms M65 and M52 use unions of orbits...

An algorithm for deciding if a polyomino tiles the plane

Ian Gambini, Laurent Vuillon (2007)

RAIRO - Theoretical Informatics and Applications

For polyominoes coded by their boundary word, we describe a quadratic O(n2) algorithm in the boundary length n which improves the naive O(n4) algorithm. Techniques used emanate from algorithmics, discrete geometry and combinatorics on words.

An aperiodicity problem for multiwords

Véronique Bruyère, Olivier Carton, Alexandre Decan, Olivier Gauwin, Jef Wijsen (2012)

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

Multiwords are words in which a single symbol can be replaced by a nonempty set of symbols. They extend the notion of partial words. A word w is certain in a multiword M if it occurs in every word that can be obtained by selecting one single symbol among the symbols provided in each position of M. Motivated by a problem on incomplete databases, we investigate a variant of the pattern matching problem which is to decide whether a word w is certain in a multiword M. We study the language CERTAIN(w)...

An aperiodicity problem for multiwords

Véronique Bruyère, Olivier Carton, Alexandre Decan, Olivier Gauwin, Jef Wijsen (2012)

RAIRO - Theoretical Informatics and Applications

Multiwords are words in which a single symbol can be replaced by a nonempty set of symbols. They extend the notion of partial words. A word w is certain in a multiword M if it occurs in every word that can be obtained by selecting one single symbol among the symbols provided in each position of M. Motivated by a problem on incomplete databases, we investigate a variant of the pattern matching problem which is to decide whether a word w is certain in a multiword M. We study the language CERTAIN(w)...

Currently displaying 81 – 100 of 133