Arrow Research search

Author name cluster

Jarett Schwartz

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers
1 author row

Possible papers

2

Highlights Conference 2013 Conference Abstract

FO model checking of interval graphs

  • Robert Ganian
  • Petr Hliněný
  • Daniel Kral
  • Jan Obdržálek
  • Jarett Schwartz
  • Jakub Teska

We study the computational complexity of the model checking problem for the first order (FO) logic on interval graphs, i. e. , interscetion graphs of intervals on the real line. As the main result we show that for n-vertex interval graphs this problem can be solved in time O(n log n) if we take intervals with lengths from a fixed finite set. On the other hand, we show that this is no longer true once the interval lengths taken from any set that is dense in some open subset.

PDF Details

TCS Journal 2012 Journal Article

Constructing partial words with subword complexities not achievable by full words

  • F. Blanchet-Sadri
  • Aleksandar Chakarov
  • Lucas Manuelli
  • Jarett Schwartz
  • Slater Stich

Partial words are sequences over a finite alphabet that may contain wildcard symbols, called holes, which match, or are compatible with, all letters in the alphabet ((full) words are just partial words without holes). The subword complexity function of a partial word w over a finite alphabet A assigns to each positive integer, n, the number, p w ( n ), of distinct full words over A that are compatible with factors of length n of w. In this paper, with the help of our so-called hole functions, we construct infinite partial words w such that p w ( n ) = Θ ( n α ) for any real number α > 1. In addition, these partial words have the property that there exist infinitely many non-negative integers m satisfying p w ( m + 1 ) − p w ( m ) ≥ m α. Combining these results with earlier ones on full words, we show that this represents a class of subword complexity functions not achievable by full words. We also construct infinite partial words with intermediate subword complexity, that is, between polynomial and exponential.

Details DOI
v2026.09.13