BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Source author record

Frank Ruskey

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record
math.COData Structures and AlgorithmsDiscrete MathematicsComputational ComplexityFormal Languages and Automata TheoryComputational Geometry

Catalog footprint

Research overview

15works
6topics
4close collaborators

Actions

Is this your work?

Log in to claim
Open graphBrowse papers

Published work

15 publications

preprint2016arXiv

On Prefix Normal Words and Prefix Normal Forms

A 11-prefix normal word is a binary word with the property that no factor has more 11s than the prefix of the same length; a 00-prefix normal word is defined analogously. These words arise in the context of indexed binary jumbled pattern matching, where the aim is to decide whether a word has a factor with a given number of 11s and 00s (a given Parikh vector). Each binary word has an associated set of Parikh vectors of the factors of the word. Using prefix normal words, we provide a characterization of the equivalence class of binary words having the same set of Parikh vectors of their factors. We prove that the language of prefix normal words is not context-free and is strictly contained in the language of pre-necklaces, which are prefixes of powers of Lyndon words. We give enumeration results on pnw(n)\textit{pnw}(n), the number of prefix normal words of length nn, showing that, for sufficiently large nn, 2n−4nlg⁡n≤pnw(n)≤2n−lg⁡n+1. 2^{n-4 \sqrt{n \lg n}} \le \textit{pnw}(n) \le 2^{n - \lg n + 1}. For fixed density (number of 11s), we show that the ordinary generating function of the number of prefix normal words of length nn and density dd is a rational function. Finally, we give experimental results on pnw(n)\textit{pnw}(n), discuss further properties, and state open problems.

Open access
preprint2015arXiv

All Simple Venn Diagrams are Hamiltonian

An nn-Venn diagram is a certain collection of nn simple closed curves in the plane. They can be regarded as graphs where the points of intersection are vertices and the curve segments between points of intersection are edges. Every nn-Venn diagram has the property that a curve touches any given face at most once between the points of intersection incident to that face. We prove that any connected collection of nn simple closed curves satisfying that property are 4-connected, if n≥3n \ge 3, so long as the curves intersect transversally and at most two curves intersect at any point. Hence by a theorem of Tutte, such collections, including simple Venn diagrams, are Hamiltonian.

Open access
preprint2015arXiv

Nested Recurrence Relations With Conolly-Like Solutions

A nondecreasing sequence of positive integers is (α,β)(α,β)-Conolly, or Conolly-like for short, if for every positive integer mm the number of times that mm occurs in the sequence is α+βrmα+ βr_m, where rmr_m is 11 plus the 2-adic valuation of mm. A recurrence relation is (α,β)(α, β)-Conolly if it has an (α,β)(α, β)-Conolly solution sequence. We discover that Conolly-like sequences often appear as solutions to nested (or meta-Fibonacci) recurrence relations of the form A(n)=∑i=1kA(n−si−∑j=1piA(n−aij))A(n) = \sum_{i=1}^k A(n-s_i-\sum_{j=1}^{p_i} A(n-a_{ij})) with appropriate initial conditions. For any fixed integers kk and p1,p2,…,pkp_1,p_2,\ldots, p_k we prove that there are only finitely many pairs (α,β)(α, β) for which A(n)A(n) can be (α,β)(α, β)-Conolly. For the case where α=0α=0 and β=1β=1, we provide a bijective proof using labelled infinite trees to show that, in addition to the original Conolly recurrence, the recurrence H(n)=H(n−H(n−2))+H(n−3−H(n−5))H(n)=H(n-H(n-2)) + H(n-3-H(n-5)) also has the Conolly sequence as a solution. When k=2k=2 and p1=p2p_1=p_2, we construct an example of an (α,β)(α,β)-Conolly recursion for every possible (α,β)α,β) pair, thereby providing the first examples of nested recursions with pi>1p_i>1 whose solutions are completely understood. Finally, in the case where k=2k=2 and p1=p2p_1=p_2, we provide an if and only if condition for a given nested recurrence A(n)A(n) to be (α,0)(α,0)-Conolly by proving a very general ceiling function identity.

Open access
preprint2014arXiv

Developing a Mathematical Model for Bobbin Lace

Bobbin lace is a fibre art form in which intricate and delicate patterns are created by braiding together many threads. An overview of how bobbin lace is made is presented and illustrated with a simple, traditional bookmark design. Research on the topology of textiles and braid theory form a base for the current work and is briefly summarized. We define a new mathematical model that supports the enumeration and generation of bobbin lace patterns using an intelligent combinatorial search. Results of this new approach are presented and, by comparison to existing bobbin lace patterns, it is demonstrated that this model reveals new patterns that have never been seen before. Finally, we apply our new patterns to an original bookmark design and propose future areas for exploration.

Open access
preprint2014arXiv

Generating Tatami Coverings Efficiently

We present two algorithms to list certain classes of monomino-domino coverings which conform to the \emph{tatami} restriction; no four tiles meet. Our methods exploit structural features of tatami coverings in order to create the lists in O(1)O(1) time per covering. This is faster than known methods for generating certain classes of matchings in bipartite graphs. We discuss tatami coverings of n×nn\times n grids with nn monominoes and vv vertical dominoes, as well as tatami coverings of a two-way infinitely-wide strip of constant height, subject to the constraint that they have a finite number of non-trivial structural "features". These two classes are representative of two differing structural characterisations of tatami coverings which may be adapted to count other classes of tatami coverings or locally restricted matchings, such as tatami coverings of rectangles.

Open access
preprint2014arXiv

Normal, Abby Normal, Prefix Normal

A prefix normal word is a binary word with the property that no substring has more 1s than the prefix of the same length. This class of words is important in the context of binary jumbled pattern matching. In this paper we present results about the number pnw(n)pnw(n) of prefix normal words of length nn, showing that pnw(n)=Ω(2n−cnln⁡n)pnw(n) =Ω\left(2^{n - c\sqrt{n\ln n}}\right) for some cc and pnw(n)=O(2n(ln⁡n)2n)pnw(n) = O \left(\frac{2^n (\ln n)^2}{n}\right). We introduce efficient algorithms for testing the prefix normal property and a "mechanical algorithm" for computing prefix normal forms. We also include games which can be played with prefix normal words. In these games Alice wishes to stay normal but Bob wants to drive her "abnormal" -- we discuss which parameter settings allow Alice to succeed.

Open access
preprint2014arXiv

On Combinatorial Generation of Prefix Normal Words

A prefix normal word is a binary word with the property that no substring has more 1s than the prefix of the same length. This class of words is important in the context of binary jumbled pattern matching. In this paper we present an efficient algorithm for exhaustively listing the prefix normal words with a fixed length. The algorithm is based on the fact that the language of prefix normal words is a bubble language, a class of binary languages with the property that, for any word w in the language, exchanging the first occurrence of 01 by 10 in w results in another word in the language. We prove that each prefix normal word is produced in O(n) amortized time, and conjecture, based on experimental evidence, that the true amortized running time is O(polylog(n)).

Open access
preprint2013arXiv

Domino Tatami Covering is NP-complete

A covering with dominoes of a rectilinear region is called \emph{tatami} if no four dominoes meet at any point. We describe a reduction from planar 3SAT to Domino Tatami Covering. As a consequence it is NP-complete to decide whether there is a perfect matching of a graph that meets every 4-cycle, even if the graph is restricted to be an induced subgraph of the grid-graph. The gadgets used in the reduction were discovered with the help of a SAT-solver.

Open access
preprint2013arXiv

Enumerating maximal tatami mat coverings of square grids with vv vertical dominoes

We enumerate a certain class of monomino-domino coverings of square grids, which conform to the \emph{tatami} restriction; no four tiles meet. Let Tn\mathbf T_{n} be the set of monomino-domino tatami coverings of the n×nn\times n grid with the maximum number, nn, of monominoes, oriented so that they have a monomino in each of the top left and top right corners. We give an algorithm for exhaustively generating the coverings in Tn\mathbf T_{n} with exactly vv vertical dominoes in constant amortized time, and an explicit formula for counting them. The polynomial that generates these counts has the factorisation {align*} P_n(z)\prod_{j\ge 1} S_{\lfloor \frac{n-2}{2^j} \rfloor}(z), {align*} where Sn(z)=∏i=1n(1+zi)S_n(z) = \prod_{i=1}^{n} (1 + z^i), and Pn(z)P_n(z) is an irreducible polynomial, at least for 1<n<200{1 < n < 200}. We present some compelling properties and conjectures about Pn(z)P_n(z). For example Pn(1)=n2ν(n−2)−1P_n(1) = n2^{ν(n-2)-1} for all n≥2n \ge 2, where ν(n)ν(n) is the number of 1s in the binary representation of nn and deg(Pn(z))=∑k=1n−2Od(k)(P_n(z)) = \sum_{k=1}^{n-2} Od(k), where Od(k)Od(k) is the largest odd divisor of kk.

Open access
preprint2013arXiv

Morphic Words and Nested Recurrence Relations

We explore a family of nested recurrence relations with arbitrary levels of nesting, which have an interpretation in terms of fixed points of morphisms over a countably infinite alphabet. Recurrences in this family are related to a number of well-known sequences, including Hofstadter's G sequence and the Conolly and Tanny sequences. For a recurrence a(n) in this family with only finitely terms, we provide necessary and sufficient conditions for the limit a(n)/n to exist.

Open access
preprint2013arXiv

Parallel and sequential in-place permuting and perfect shuffling using involutions

We show that any permutation of 1,2,...,N{1,2,...,N} can be written as the product of two involutions. As a consequence, any permutation of the elements of an array can be performed in-place in parallel in time O(1). In the case where the permutation is the kk-way perfect shuffle we develop two methods for efficiently computing such a pair of involutions. The first method works whenever NN is a power of kk; in this case the time is O(N) and space O(log⁡2N)O(\log^2 N). The second method applies to the general case where NN is a multiple of kk; here the time is O(Nlog⁡N)O(N \log N) and the space is O(log⁡2N)O(\log^2 N). If k=2k=2 the space usage of the first method can be reduced to O(log⁡N)O(\log N) on a machine that has a SADD (population count) instruction.

Open access
preprint2012arXiv

A New Rose : The First Simple Symmetric 11-Venn Diagram

A symmetric Venn diagram is one that is invariant under rotation, up to a relabeling of curves. A simple Venn diagram is one in which at most two curves intersect at any point. In this paper we introduce a new property of Venn diagrams called crosscut symmetry, which is related to dihedral symmetry. Utilizing a computer search restricted to crosscut symmetry we found many simple symmetric Venn diagrams with 11 curves. This answers an existence question that has been open since the 1960's. The first such diagram that was discovered is shown here.

Open access
preprint2012arXiv

An Undecidable Nested Recurrence Relation

Roughly speaking, a recurrence relation is nested if it contains a subexpression of the form ... A(...A(...)...). Many nested recurrence relations occur in the literature, and determining their behavior seems to be quite difficult and highly dependent on their initial conditions. A nested recurrence relation A(n) is said to be undecidable if the following problem is undecidable: given a finite set of initial conditions for A(n), is the recurrence relation calculable? Here calculable means that for every n >= 0, either A(n) is an initial condition or the calculation of A(n) involves only invocations of A on arguments in {0,1,...,n-1}. We show that the recurrence relation A(n) = A(n-4-A(A(n-4)))+4A(A(n-4)) +A(2A(n-4-A(n-2))+A(n-2)). is undecidable by showing how it can be used, together with carefully chosen initial conditions, to simulate Post 2-tag systems, a known Turing complete problem.

Open access
preprint2012arXiv

Isoperimetric Sequences for Infinite Complete Binary Trees, Meta-Fibonacci Sequences and Signed Almost Binary Partitions

In this paper we demonstrate connections between three seemingly unrelated concepts. (1) The discrete isoperimetric problem in the infinite binary tree with all the leaves at the same level, T∞ {\mathcal T}_{\infty}: The nn-th edge isoperimetric number δ(n)δ(n) is defined to be min⁡∣S∣=n,S⊂V(T∞)∣(S,Sˉ)∣\min_{|S|=n, S \subset V({\mathcal T}_{\infty})} |(S,\bar{S})|, where (S,Sˉ)(S,\bar{S}) is the set of edges in the cut defined by SS. (2) Signed almost binary partitions: This is the special case of the coin-changing problem where the coins are drawn from the set ${\pm (2^d - 1): $d$ is a positive integer}$. The quantity of interest is τ(n)τ(n), the minimum number of coins necessary to make change for nn cents. (3) Certain Meta-Fibonacci sequences: The Tanny sequence is defined by T(n)=T(n−1−T(n−1))+T(n−2−T(n−2))T(n)=T(n{-}1{-}T(n{-}1))+T(n{-}2{-}T(n{-}2)) and the Conolly sequence is defined by C(n)=C(n−C(n−1))+C(n−1−C(n−2))C(n)=C(n{-}C(n{-}1))+C(n{-}1{-}C(n{-}2)), where the initial conditions are T(1)=C(1)=T(2)=C(2)=1T(1) = C(1) = T(2) = C(2) = 1. These are well-known "meta-Fibonacci" sequences. The main result that ties these three together is the following: δ(n)=τ(n)=n+2+2min⁡1≤k≤n(C(k)−T(n−k)−k). δ(n) = τ(n) = n+ 2 + 2 \min_{1 \le k \le n} (C(k) - T(n-k) - k). Apart from this, we prove several other results which bring out the interconnections between the above three concepts.

Open access
preprint2011arXiv

Auspicious tatami mat arrangements

An \emph{auspicious tatami mat arrangement} is a tiling of a rectilinear region with two types of tiles, 1×21 \times 2 tiles (dimers) and 1×11 \times 1 tiles (monomers). The tiles must cover the region and satisfy the constraint that no four corners of the tiles meet; such tilings are called \emph{tatami tilings}. The main focus of this paper is when the rectilinear region is a rectangle. We provide a structural characterization of rectangular tatami tilings and use it to prove that the tiling is completely determined by the tiles that are on its border. We prove that the number of tatami tilings of an n×nn \times n square with nn monomers is n2n−1n2^{n-1}. We also show that, for fixed-height, the generating function for the number of tatami tilings of a rectangle is a rational function, and outline an algorithm that produces the generating function.

Open access

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.