Back to Search
Start Over
Proving properties of some greedily-defined integer recurrences via automata theory.
- Source :
-
Theoretical Computer Science . Mar2024, Vol. 988, pN.PAG-N.PAG. 1p. - Publication Year :
- 2024
-
Abstract
- Venkatachala on the one hand, and Avdispahić & Zejnulahi on the other, both studied 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 software Walnut. Using these ideas, we can prove a conjecture of Quet and find connections between Quet's sequence and the "married" functions of Hofstadter. • Uses a new technique, automata theory, to prove properties of some greedily-defined integer sequences. • Finds much simpler proofs of some known results in the literature. • Finds a new connection between Quet's sequence and the Hofstadter married functions. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 988
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 175190717
- Full Text :
- https://doi.org/10.1016/j.tcs.2023.114363