Back to Search
Start Over
A General Approach to Proving Properties of Fibonacci Representations via Automata Theory
- Source :
- EPTCS 386, 2023, pp. 228-242
- Publication Year :
- 2023
-
Abstract
- We provide a method, based on automata theory, to mechanically prove the correctness of many numeration systems based on Fibonacci numbers. With it, long case-based and induction-based proofs of correctness can be replaced by simply constructing a regular expression (or finite automaton) specifying the rules for valid representations, followed by a short computation. Examples of the systems that can be handled using our technique include Brown's lazy representation (1965), the far-difference representation developed by Alpert (2009), and three representations proposed by Hajnal (2023). We also provide three additional systems and prove their validity.<br />Comment: In Proceedings AFL 2023, arXiv:2309.01126
Details
- Database :
- arXiv
- Journal :
- EPTCS 386, 2023, pp. 228-242
- Publication Type :
- Report
- Accession number :
- edsarx.2309.02765
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.4204/EPTCS.386.18