ID: 1311.4776

A Case Study in Meta-AUTOMATION: AUTOMATIC Generation of Congruence AUTOMATA For Combinatorial Sequences

November 19, 2013

View on ArXiv
Eric Rowland, Doron Zeilberger
Mathematics
Combinatorics

This article is a sequel to a recent article by Eric Rowland and Reem Yassawi, presenting yet another approach to the fast determination of congruence properties of `famous' combinatorial sequences. The present approach can be taught to a computer, and our beloved servant, Shalosh B. Ekhad, was able to generate many new theorems, for famous sequences, of course, but also for many obscure ones!

Similar papers 1

Congruence properties of combinatorial sequences via Walnut and the Rowland-Yassawi-Zeilberger automaton

October 12, 2021

91% Match
Narad Rampersad, Jeffrey Shallit
Combinatorics
Formal Languages and Automat...
Number Theory

Certain famous combinatorial sequences, such as the Catalan numbers and the Motzkin numbers, when taken modulo a prime power, can be computed by finite automata. Many theorems about such sequences can therefore be proved using Walnut, which is an implementation of a decision procedure for proving various properties of automatic sequences. In this paper we explore some results (old and new) that can be proved using this method.

Find SimilarView on arXiv

Automatic Theorem Proving in Walnut

March 18, 2016

88% Match
Hamoon Mousavi
Formal Languages and Automat...
Logic in Computer Science
Mathematical Software
Combinatorics

Walnut is a software package that implements a mechanical decision procedure for deciding certain combinatorial properties of some special words referred to as automatic words or automatic sequences. Walnut is written in Java and is open source. It is licensed under GNU General Public License.

Find SimilarView on arXiv

A Congruence-based Perspective on Automata Minimization Algorithms

June 14, 2019

87% Match
Pierre Ganty, Elena Gutiérrez, Pedro Valero
Formal Languages and Automat...

In this work we use a framework of finite-state automata constructions based on equivalences over words to provide new insights on the relation between well-known methods for computing the minimal deterministic automaton of a language.

Find SimilarView on arXiv

Automatic congruences for diagonals of rational functions

October 31, 2013

87% Match
Eric Rowland, Reem Yassawi
Number Theory
Symbolic Computation
Combinatorics

In this paper we use the framework of automatic sequences to study combinatorial sequences modulo prime powers. Given a sequence whose generating function is the diagonal of a rational power series, we provide a method, based on work of Denef and Lipshitz, for computing a finite automaton for the sequence modulo $p^\alpha$, for all but finitely many primes $p$. This method gives completely automatic proofs of known results, establishes a number of new theorems for well-known ...

Find SimilarView on arXiv

Automatic Theorem-Proving in Combinatorics on Words

March 16, 2012

87% Match
Dane Henshall, Jeffrey Shallit
Formal Languages and Automat...
Logic in Computer Science

We describe a technique for mechanically proving certain kinds of theorems in combinatorics on words, using automata and a package for manipulating them. We illustrate our technique by solving, purely mechanically, an open problem of Currie and Saari on the lengths of unbordered factors in the Thue-Morse sequence.

Find SimilarView on arXiv

Proving properties of some greedily-defined integer recurrences via automata theory

August 12, 2023

87% Match
Jeffrey Shallit
Discrete Mathematics
Formal Languages and Automat...
Combinatorics

Venkatachala on the one hand, and Avdispahi\'c & Zejnulahi on the other, both studiied integer sequences with an unusual sum property defined in a greedy way, and proved many results about them. However, their proofs were rather lengthy and required numerous cases. In this paper, I provide a different approach, via finite automata, that can prove the same results (and more) in a simple, unified way. Instead of case analysis, we use a decision procedure implemented in the free...

Find SimilarView on arXiv

Automated Discovery and Proof of Congruence Theorems for Partial Sums of Combinatorial Sequences

September 30, 2015

87% Match
William Y. C. Chen, Qing-Hu Hou, Doron Zeilberger
Combinatorics

Many combinatorial sequences (for example, the Catalan and Motzkin numbers) may be expressed as the constant term of $P(x)^k Q(x)$, for some Laurent polynomials $P(x)$ and $Q(x)$ in the variable $x$ with integer coefficients. Denoting such a sequence by $a_k$, we obtain a general formula that determines the congruence class, modulo $p$, of the indefinite sum $\sum_{k=0}^{rp -1} a_k$, for {\it any} prime $p$, and any positive integer $r$, as a linear combination of sequences t...

Find SimilarView on arXiv

Transduction of Automatic Sequences and Applications

March 27, 2023

86% Match
Jeffrey Shallit, Anatoly Zavyalov
Formal Languages and Automat...
Discrete Mathematics
Combinatorics

We consider the implementation of the transduction of automatic sequences, and their generalizations, in the Walnut software for solving decision problems in combinatorics on words. We provide a number of applications, including (a) representations of n! as a sum of three squares (b) overlap-free Dyck words and (c) sums of Fibonacci representations. We also prove results about iterated running sums of the Thue-Morse sequence.

Find SimilarView on arXiv

Automated Proofs of Many Conjectured Recurrences in the OEIS made by R.J. Mathar

July 14, 2017

86% Match
Shalosh B. Ekhad, Mingjia Yang, Doron Zeilberger
History and Overview
Combinatorics

The On-Line Encyclopedia Of Integer Sequences , that wonderful resource that most combinatorialists, and many other mathematicians and scientists, use at least once a day, is a treasure trove of mathematical information, and, one of its charms is that it contains many intriguing conjectures. But one should be on one's guard, because some of the conjectures are either already theorems, or can be routinely proved. In this case study we demonstrate, and actually fully implement ...

Find SimilarView on arXiv

Automata and automatic sequences

December 17, 2022

86% Match
Jean-Paul Allouche, Michel Mendès France
Formal Languages and Automat...
Discrete Mathematics
Number Theory

In the following pages we discuss infinite sequences defined on a finite alphabet, and more specially those which are generated by finite automata. We have divided our paper into seven parts which are more or less self-contained. Needless to say, we feel that the order we propose is the most natural one. References appear at the end of each one of the parts which implies some redundancy. Extra references are listed at the very end of our paper.

Find SimilarView on arXiv