1,720,990 research outputs found
On prefix normal words and prefix normal forms
No full textA 1-prefix normal word is a binary word with the property that no factor has more 1s than the prefix of the same length; a 0-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 1s and 0s (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), the number of prefix normal words of length n, showing that, for sufficiently large n, 2n−4nlgn≤pnw(n)≤2n−lgn+1. For fixed density (number of 1s), we show that the ordinary generating function of the number of prefix normal words of length n and density d is a rational function. Finally, we give experimental results on pnw(n), discuss further properties, and state open problem
Fast algorithms to generate restricted classes of strings under rotation
No full textA necklace is a representative of an equivalence class of k-ary strings under rotation. Efficient algorithms for generating (i.e., listing) necklaces have been known for some time. Many applications, however, require a restricted class of necklaces for which no efficient generation algorithm previously existed. This dissertation addresses this problem by developing fast algorithms to generate the following restricted classes of necklaces: (a) unlabeled necklaces, (b) fixed density necklaces, (c) necklaces where the number of each alphabet symbol is fixed, (d) chord diagrams, (e) necklaces which avoid a particular Lyndon substring, and (f) bracelets. An analysis for each algorithm (a), (b), (e), and (f) shows that the amount of computation is proportional to the number of strings produced. Experimental results give a strong indication that the algorithms for (c) and (d) also achieve this time bound. In addition, a new derivation of the known formula for counting chord diagrams is presented, along with a linear time algorithm to generate a basis for the n-th homogeneous component of the free Lie algebra.Graduat
Symmetries of Venn diagrams on the sphere
No full textA diagram on a surface is a collection of coloured simple closed curves which generally intersect only at points, and a Venn diagram of n curves has the additional property that there are exactly 2^n faces in the diagram, each corresponding to a unique intersection of the interiors of a subset of the curves. A diagram has rotational symmetry if it can be constructed by rotating a single closed curve in the plane n times, each time by 2 \pi /n, and changing the colour of the curve for each rotation; equivalently, the diagram can be constructed from a region forming a "pie-slice" of the diagram and containing a
section of each curve, and then copying and rotating this region n times, recolouring the sections of curves in the region appropriately. This and reflective symmetries are the only non-trivial ways a finite plane diagram can have some kind of symmetry.
In this thesis, we extend the notion of planar symmetries for diagrams onto the sphere by constructing and projecting diagrams onto the sphere and examining the much richer symmetry groups that result. Restricting our attention to Venn diagrams gives a rich combinatorial structure to the
diagrams that we examine and exploit. We derive several constructions of Venn diagrams with interesting symmetries on the sphere by modifying the landmark work of Griggs, Killian and Savage from 2004 which provided
some important answers to questions about planar symmetric diagrams. We examine a class of diagrams that exhibit a rotary reflection symmetry (a rotation of the sphere followed by a reflection), in which we make
some initial steps towards a general construction for n-Venn diagrams realizing a very rich symmetry group of order 2n, for n prime or a power of two. We also provide a many-dimensional construction of very simple Venn diagrams which realize any subgroup of an important type of symmetry group that use only reflection symmetries. In summary, we exhibit and examine at least one Venn diagram realizing each of the 14 possible different classes of finite symmetry groups on the
sphere, many of these diagrams with different types of colour symmetry. All of these investigations are coupled with a theoretical and practical framework for further investigation of symmetries of diagrams and discrete combinatorial objects on spheres and higher-dimensional surfaces
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Face-balanced, Venn and polyVenn diagrams
No full textA \emph{simple} -\emph{Venn diagram} is a collection of simple intersecting closed curves in the plane where exactly two curves meet at any intersection point;
the curves divide the plane into distinct open regions, each defined by its intersection of the interior or exterior of each of the curves.
A Venn diagram is \emph{reducible} if there is a curve that, when removed, leaves a Venn diagram with one less curve and \emph{irreducible} if no such curve exists.
A Venn diagram is \emph{extendible} if another curve can be added, producing a Venn diagram with one more curve.
Currently it is not known whether every simple Venn diagram is extendible by the addition of another curve.
We show that all simple Venn diagrams with curves or less are extendible to another simple Venn diagram.
We also show that for certain Venn diagrams, a new extending curve is relatively easy to produce.
We define a new type of diagram of simple closed curves where each curve divides the plane into an equal number of regions;
we call such a diagram a \emph{face-balanced} diagram.
We generate and exhibit all face-balanced diagrams up to and including those with regions;
these include all the Venn diagrams.
Venn diagrams exist where the curves are the perimeters of polyominoes drawn on the integer lattice.
When each of the intersection regions is a single unit square, we call these \emph{minimum area polyomino Venn diagrams}, or \emph{polyVenns}.
We show that polyVenns can be constructed and confined in bounding rectangles of size whenever and .
We show this using two constructive proofs that extend existing diagrams.
Finally, for even , we construct polyVenns with polyominoes in bounding rectangles in which the empty set is not represented as a unit [email protected]
Searching for Simple Symmetric Venn Diagrams
No full textAn n-Venn diagram is defined as a collection of n finitely intersecting closed curves dividing the plane into 2^n distinct regions, where each region is in the interior of a unique subset of the curves. A Venn diagram is simple if at most two curves intersect at any point, and it is monotone if it has some embedding on the plane in which all curves are convex. An n-Venn diagram has n-fold rotational symmetry if a rotation of 180 degrees about a centre point in the plane leaves the diagram unchanged, up to a relabeling of the curves. It has been known that rotationally symmetric Venn diagrams could exist only if the number of curves is prime. Moreover, non-simple Venn diagrams with rotational symmetry have been proven to exist for any prime number of curves. However, the largest prime for which a simple rotationally symmetric Venn diagram was known prior to this, was 7. In this thesis, we are concerned with generating simple monotone Venn diagrams, especially those that have some type(s) of symmetry. Several representations of these diagrams are introduced and different backtracking search algorithms are provided based on these representations. Using these algorithms we show that there are 39,020 non-isomorphic simple monotone 6-Venn diagrams in total. In the case of drawing Venn diagrams on a sphere, we prove that there exists a simple symmetric n-Venn diagram, for any n >= 6, with the following set(s) of isometries : (a) a 4-fold rotational symmetry about the polar axis, together with an additional involutional symmetry about an axis through the equator, or (b) an involutional symmetry about the polar axis together with two reflectional
symmetries about orthogonal planes that intersect at the polar axis. Finally, we introduce a new type of symmetry of Venn diagrams which leads us to the discovery of the first simple rotationally symmetric Venn diagrams of 11 and 13 [email protected]
Monomino-Domino Tatami Coverings
No full textWe present several new results on the combinatorial properties of a locally restricted version of monomino-domino coverings of rectilinear regions. These are monomino-domino tatami coverings, and the restriction is that no four tiles may meet at any point. The global structure that the tatami restriction induces has numerous implications, and provides a powerful tool for solving enumeration problems on tatami coverings. Among these we address the enumeration of coverings of rectangles, with various parameters, and we develop algorithms for exhaustive generation of coverings, in constant amortised time per covering. We also con- sider computational complexity on two fronts; firstly, the structure shows that the space required to store a covering of the rectangle is linear in its longest dimension, and secondly, it is NP-complete to decide whether an arbitrary polyomino can be tatami-covered only with [email protected]
Lace tessellations: a mathematical model for bobbin lace and an exhaustive combinatorial search for patterns
Full text linkBobbin lace is a 500-year-old art form in which threads are braided together in an alternating manner to produce a lace fabric. A key component in its construction is a small
pattern, called a bobbin lace ground, that can be repeated periodically to fill a region of
any size. In this thesis we present a mathematical model for bobbin lace grounds representing the structure as the pair (Δ(G), ζ (v)) where Δ(G) is a topological embedding of a 2-regular digraph, G, on a torus and ζ(v) is a mapping from the vertices of G to a set of braid words. We explore in depth the properties that Δ(G) must possess in order to produce workable lace patterns. Having developed a solid, logical foundation for bobbin lace grounds, we enumerate and exhaustively generate patterns that conform to that model. We start by specifying an equivalence relation and define what makes a pattern prime so that we can identify unique representatives. We then prove that there are an infinite number of prime workable patterns. One of the key properties identified in the
model is that it must be possible to partition Δ(G) into a set of osculating circuits such
that each circuit has a wrapping index of (1,0); that is, the circuit wraps once around
the meridian of the torus and does not wrap around the longitude. We use this property
to exhaustively generate workable patterns for increasing numbers of vertices in G by
gluing together lattice paths in an osculating manner. Using a backtracking algorithm to process the lattice paths, we identify over 5 million distinct prime patterns. This is well in
excess of the roughly 1,000 found in lace ground catalogues. The lattice paths used in our
approach are members of a family of partially directed lattice paths that have not been
previously reported. We explore these paths in detail, develop a recurrence relation and
generating function for their enumeration and present a bijection between these paths
and a subset of Motzkin paths. Finally, to draw out of the extremely large number of patterns some of the more aesthetically interesting cases for lacemakers to work on, we look for examples that have a high degree of symmetry. We demonstrate, by computational generation, that there are lace ground representatives from each of the 17 planar periodic symmetry [email protected]
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
- …
