Addition machines, automatic functions and open problems of Floyd and Knuth

DOI10.1016/j.jcss.2023.04.003arXiv2111.08969OpenAlexW4365151114MaRDI QIDQ6098150

Frank Stephan, Ammar Fathin Sabili, Xiaodong Jia, Sanjay Jain

Publication date: 12 June 2023

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2111.08969

zbMATH Keywords

additionintegersabstract complexityautomatic functionssubtraction and order as primitive operations

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Trusted computing with addition machines. I
• Division in idealized unit cost RAMs
• Presburgerness of predicates regular in two number systems
• Fast direct computation of modular reduction
• Semiautomatic structures
• Trusted computing with addition machines. II
• Finite presentations of infinite structures: Automata and interpretations
• Fibonacci linear forms and parallel arithmetic algorithms for large numbers
• Integer multiplication in time \(O(n\log n)\)
• A computation model with automatic functions and relations as primitive operations
• Automatic functions, linear time and learning
• Three Lectures on Automatic Structures
• Weak Second‐Order Arithmetic and Finite Automata
• Primality and identity testing via Chinese remaindering
• Addition Machines
• Automata Presenting Structures: A Survey of the Finite String Case
• Algebraic Complexity Theory
• Automatic Structures
• On the base-dependence of sets of numbers recognizable by finite automata
• Algorithms