BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
J. Shallit appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We show that the first-order logical theory of the binary overlap-free words (and, more generally, the $α$-free words for rational $α$, $2 < α \leq 7/3$), is decidable. As a consequence, many results previously obtained about this class through tedious case- based proofs can now be proved "automatically", using a decision procedure.
We prove a number of conjectures [arXiv:2005.04066] recently stated by P. Barry, related to the paperfolding sequence and the Rueppel sequence.
We prove three conjectures, related to the paperfolding sequence, in a recent paper [arXiv:2005.04066] of P. Barry.
We find an explicit closed form for the subword complexity of the infinite fixed point of the morphism sending $a \rightarrow aab$ and $b \rightarrow b$. This morphism is then generalized in three different ways, and we find similar explicit expressions for the subword complexity of the generalizations.
Following up on a paper of Balamohan, Kuznetsov, and Tanny, we analyze a variant of Hofstadter's Q-sequence and show it is 2-automatic. An automaton computing the sequence is explicitly given.
We consider a set of natural operations on languages, and prove that the orbit of any language L under the monoid generated by this set is finite and bounded, independently of L. This generalizes previous results about complement, Kleene closure, and positive closure.
We consider various shuffling and unshuffling operations on languages and words, and examine their closure properties. Although the main goal is to provide some good and novel exercises and examples for undergraduate formal language theory classes, we also provide some new results and some open problems.
Motivated by the known autocorrelation properties of the Rudin-Shapiro sequence, we study the discrete correlation among infinite sequences over a finite alphabet, where we just take into account whether two symbols are identical. We show by combinatorial means that sequences cannot be "too" different, and by an explicit construction generalizing the Rudin-Shapiro sequence, we show that we can achieve the maximum possible difference.