skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Symbol Separation in Double Occurrence Words
A double occurrence word (DOW) is a word in which every symbol appears exactly twice. We define the symbol separation of a DOW [Formula: see text] to be the number of letters between the two copies of a symbol, and the separation of [Formula: see text] to be the sum of separations over all symbols in [Formula: see text]. We then analyze relationship among size, reducibility and separation of DOWs. Specifically, we provide tight bounds of separations of DOWs with a given size and characterize the words that attain those bounds. We show that all separation numbers within the bounds can be realized. We present recursive formulas for counting the numbers of DOWs with a given separation under various restrictions, such as the number of irreducible factors. These formulas can be obtained by inductive construction of all DOWs with the given separation.  more » « less
Award ID(s):
1764406 1800443
PAR ID:
10254017
Author(s) / Creator(s):
; ; ;
Date Published:
Journal Name:
International Journal of Foundations of Computer Science
Volume:
31
Issue:
07
ISSN:
0129-0541
Page Range / eLocation ID:
915 to 928
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; (, Discrete Mathematics, Algorithms and Applications)
    The special purpose sorting operation, context directed swap (CDS), is an example of the block interchange sorting operation studied in prior work on permutation sorting. CDShas been postulated to model certain molecular sorting events that occur in the genome maintenance program of some species of ciliates. We investigate the mathematical structure of permutations not sortable by the CDSsorting operation. In particular, we present substantial progress towards quantifying permutations with a given strategic pile size, which can be understood as a measure of CDSnon-sortability. Our main results include formulas for the number of permutations in [Formula: see text] with maximum size strategic pile. More generally, we derive a formula for the number of permutations in [Formula: see text] with strategic pile size [Formula: see text], in addition to an algorithm for computing certain coefficients of this formula, which we call merge numbers. 
    more » « less
  2. ; ; ; ; ; ; ; ; ; ; et al (, Journal of Knot Theory and Its Ramifications)
    Meier and Zupan proved that an orientable surface [Formula: see text] in [Formula: see text] admits a tri-plane diagram with zero crossings if and only if [Formula: see text] is unknotted, so that the crossing number of [Formula: see text] is zero. We determine the minimal crossing numbers of nonorientable unknotted surfaces in [Formula: see text], proving that [Formula: see text], where [Formula: see text] denotes the connected sum of [Formula: see text] unknotted projective planes with normal Euler number [Formula: see text] and [Formula: see text] unknotted projective planes with normal Euler number [Formula: see text]. In addition, we convert Yoshikawa’s table of knotted surface ch-diagrams to tri-plane diagrams, finding the minimal bridge number for each surface in the table and providing upper bounds for the crossing numbers. 
    more » « less
  3. ; (, Journal of Mathematical Logic)
    Fix a weakly minimal (i.e. superstable [Formula: see text]-rank [Formula: see text]) structure [Formula: see text]. Let [Formula: see text] be an expansion by constants for an elementary substructure, and let [Formula: see text] be an arbitrary subset of the universe [Formula: see text]. We show that all formulas in the expansion [Formula: see text] are equivalent to bounded formulas, and so [Formula: see text] is stable (or NIP) if and only if the [Formula: see text]-induced structure [Formula: see text] on [Formula: see text] is stable (or NIP). We then restrict to the case that [Formula: see text] is a pure abelian group with a weakly minimal theory, and [Formula: see text] is mutually algebraic (equivalently, weakly minimal with trivial forking). This setting encompasses most of the recent research on stable expansions of [Formula: see text]. Using various characterizations of mutual algebraicity, we give new examples of stable structures of the form [Formula: see text]. Most notably, we show that if [Formula: see text] is a weakly minimal additive subgroup of the algebraic numbers, [Formula: see text] is enumerated by a homogeneous linear recurrence relation with algebraic coefficients, and no repeated root of the characteristic polynomial of [Formula: see text] is a root of unity, then [Formula: see text] is superstable for any [Formula: see text]. 
    more » « less
  4. ; (, International Journal of Computational Geometry & Applications)
    null (Ed.)
    We propose an Euler transformation that transforms a given [Formula: see text]-dimensional cell complex [Formula: see text] for [Formula: see text] into a new [Formula: see text]-complex [Formula: see text] in which every vertex is part of the same even number of edges. Hence every vertex in the graph [Formula: see text] that is the [Formula: see text]-skeleton of [Formula: see text] has an even degree, which makes [Formula: see text] Eulerian, i.e., it is guaranteed to contain an Eulerian tour. Meshes whose edges admit Eulerian tours are crucial in coverage problems arising in several applications including 3D printing and robotics. For [Formula: see text]-complexes in [Formula: see text] ([Formula: see text]) under mild assumptions (that no two adjacent edges of a [Formula: see text]-cell in [Formula: see text] are boundary edges), we show that the Euler transformed [Formula: see text]-complex [Formula: see text] has a geometric realization in [Formula: see text], and that each vertex in its [Formula: see text]-skeleton has degree [Formula: see text]. We bound the numbers of vertices, edges, and [Formula: see text]-cells in [Formula: see text] as small scalar multiples of the corresponding numbers in [Formula: see text]. We prove corresponding results for [Formula: see text]-complexes in [Formula: see text] under an additional assumption that the degree of a vertex in each [Formula: see text]-cell containing it is [Formula: see text]. In this setting, every vertex in [Formula: see text] is shown to have a degree of [Formula: see text]. We also present bounds on parameters measuring geometric quality (aspect ratios, minimum edge length, and maximum angle of cells) of [Formula: see text] in terms of the corresponding parameters of [Formula: see text] for [Formula: see text]. Finally, we illustrate a direct application of the proposed Euler transformation in additive manufacturing. 
    more » « less
  5. (, Journal of Knot Theory and Its Ramifications)
    The non-orientable 4-genus of a knot [Formula: see text] in [Formula: see text] is defined to be the minimum first Betti number of a non-orientable surface [Formula: see text] smoothly embedded in [Formula: see text] so that [Formula: see text] bounds [Formula: see text]. We will survey the tools used to compute the non-orientable 4-genus, and use various techniques to calculate this invariant for non-alternating 11 crossing knots. We will also view obstructions to a knot bounding a Möbius band given by the double branched cover of [Formula: see text] branched over [Formula: see text]. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email