Jeffrey O. Shallit

CSL Conference 2022 Conference Paper

Decidability for Sturmian Words

• Philipp Hieronymi
• Dun Ma
• Reed Oei
• Luke Schaeffer
• Christian Schulz 0013
• Jeffrey O. Shallit

We show that the first-order theory of Sturmian words over Presburger arithmetic is decidable. Using a general adder recognizing addition in Ostrowski numeration systems by Baranwal, Schaeffer and Shallit, we prove that the first-order expansions of Presburger arithmetic by a single Sturmian word are uniformly ω-automatic, and then deduce the decidability of the theory of the class of such structures. Using an implementation of this decision algorithm called Pecan, we automatically reprove classical theorems about Sturmian words in seconds, and are able to obtain new results about antisquares and antipalindromes in characteristic Sturmian words.

TCS Journal 2020 Journal Article

Unique decipherability in formal languages

• Paul C. Bell
• Daniel Reidenbach
• Jeffrey O. Shallit

We consider several language-theoretic aspects of various notions of unique decipherability (or unique factorization) in formal languages. Given a language L at some position within the Chomsky hierarchy, we investigate the language of words UD ( L ) in L ⁎ that have unique factorization over L. We also consider similar notions for weaker forms of unique decipherability, such as numerically decipherable words ND ( L ), multiset decipherable words MSD ( L ) and set decipherable words SD ( L ). Although these notions of unique factorization have been considered before, it appears that the languages of words having these properties have not been positioned in the Chomsky hierarchy up until now. We show that UD ( L ), ND ( L ), MSD ( L ) and SD ( L ) need not be context-free if L is context-free. In fact ND ( L ) and MSD ( L ) need not be context-free even if L is finite, although UD ( L ) and SD ( L ) are regular in this case. We show that if L is context-sensitive, then so are UD ( L ), ND ( L ), MSD ( L ) and SD ( L ). We also prove that the membership problem (resp. , emptiness problem) for these classes is PSPACE-complete (resp. , undecidable). We finally determine upper and lower bounds on the length of the shortest word of L ⁎ not having the various forms of unique decipherability into elements of L.

MFCS Conference 2018 Conference Paper

Lagrange's Theorem for Binary Squares

• P. Madhusudan
• Dirk Nowotka
• Aayush Rajasekaran
• Jeffrey O. Shallit

We show how to prove theorems in additive number theory using a decision procedure based on finite automata. Among other things, we obtain the following analogue of Lagrange's theorem: every natural number > 686 is the sum of at most 4 natural numbers whose canonical base-2 representation is a binary square, that is, a string of the form xx for some block of bits x. Here the number 4 is optimal. While we cannot embed this theorem itself in a decidable theory, we show that stronger lemmas that imply the theorem can be embedded in decidable theories, and show how automated methods can be used to search for these stronger lemmas.

MFCS Conference 2004 Conference Paper

A Generalization of Repetition Threshold

• Lucian Ilie
• Pascal Ochem
• Jeffrey O. Shallit

Abstract Brandenburg and (implicitly) Dejean introduced the concept of repetition threshold: the smallest real number α such that there exists an infinite word over a k -letter alphabet that avoids β -powers for all β > α. We generalize this concept to include the lengths of the avoided words. We give some conjectures supported by numerical evidence and prove three of these conjectures. As a consequence of one of our results, we show that the pattern ABCBABC is 2-avoidable. This resolves a question left open in Cassaigne’s thesis.

MFCS Conference 2001 Conference Paper

Variations on a Theorem of Fine & Wilf

• Filippo Mignosi
• Jeffrey O. Shallit
• Ming-wei Wang

Abstract In 1965, Fine & Wilf proved the following theorem: if ( f n ) n≥0 and ( g n ) n ≥0 are periodic sequences of real numbers, of periods h and k respectively, and f n = g n for 0 ≤ n < h + k - gcd( h, k ), then f n = g n for all n ≥0. Furthermore, the constant h + k - gcd( h, k ) is best possible. In this paper we consider some variations on this theorem. In particular, we study the case where f n ≤ g n instead of f n = g n. We also obtain a generalization to more than two periods.

SODA Conference 1999 Conference Paper

An Efficient Algorithm for Computing the i th letter of 4 n a

• Jeffrey O. Shallit
• David Swart

MFCS Conference 1996 Conference Paper

Polynomial Automaticity, Context-Free Languages, and Fixed Points of Morphism (Extended Abstract)

• Ian Glaister
• Jeffrey O. Shallit

Abstract If L is a formal language, we define A L ( n ) to be the number of states in the smallest deterministic finite automaton that accepts a language that agrees with L on all inputs of length ≤ n. This measure is called automaticity. In this paper, we first study the closure properties of the class DPA of languages of deterministic polynomial automaticity, i. e. , those languages L for which there exists k such that A L ( n )= O ( n k ). Next, we discuss similar results for a nondeterministic analogue of automaticity, introducing the classes NPA (languages of nondeterministic polynomial automaticity) and NPLA (languages of nondeterministic poly-log automaticity). We then show how to construct a context-free language with automaticity arbitrarily close to the maximum possible. Finally, we conclude with some remarks about the automaticity of sequences, focusing on fixed points of homomorphisms.

MFCS Conference 1992 Conference Paper

Characterizing Regular Languages with Polynomial Densities

• Andrew Szilard
• Sheng Yu 0001
• Kaizhong Zhang
• Jeffrey O. Shallit

Abstract A language L is said to have a polynomial density if the function pL. ( n )=¦L∩∑ n ¦ of L is bounded by a polynomial. We show that the function p R ( n ) of a regular language R is O ( n k ), for some k ≥0, if and only if R can be represented as a finite union of the regular expressions of the form xy * 1 z 1. .. y * t z t with a nonnegative integer t ≤ k +1, where x, y 1, z 1, .. ., y t, z t are all strings in ∑ *. We prove a characterization for the (restricted) starheight-one languages. We show that a regular language is starheight one if and only if it is the image of a regular language of polynomial density under a finite substitution. We also show that the set of starheight-one languages includes all the regular languages with polynomial densities and their complements.

SODA Conference 1990 Conference Paper

Factor Refinement

• Eric Bach 0001
• James R. Driscoll
• Jeffrey O. Shallit

FOCS Conference 1985 Conference Paper

Factoring with Cyclotomic Polynomials

• Eric Bach 0001
• Jeffrey O. Shallit

This paper discusses some new integer factoring methods involving cyclotomic polynomials. There are several polynomials f(X) known to have the following property: given a multiple of f(p), we can quickly split any composite number that has p as a prime divisor. For example -- taking f(X) to be X- 1 -- a multiple of p - 1 will suffice to easily factor any multiple of p, using an algorithm of Pollard. Other methods (due to Guy, Williams, and Judd) make use of X + 1, X2 + 1, and X2 ± X + 1. We show that one may take f to be Φk, the k-th cyclotomic polynomial. In constrast to the ad hoc methods used previously, we give a universal construction based on algebraic number theory that subsumes all the above results. Assuming generalized Riemann hypotheses, the expected time to factor N (given a multiple E of Φk(p)) is bounded by a polynomial in k, logE, and logN.

STOC Conference 1984 Conference Paper

Sums of Divisors, Perfect Numbers, and Factoring (Extended Abstract)

• Eric Bach 0001
• Gary L. Miller
• Jeffrey O. Shallit