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

DOI10.1016/J.JCSS.2023.04.003MaRDI QIDQ6098150zbMATH OpenOpenAlexFDO

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

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

abstract complexityadditionautomatic functionsintegerssubtraction and order as primitive operations

Mathematics Subject Classification ID

Computer science (68-XX)

Abstract: Floyd and Knuth investigated in 1990 register machines which can add, subtract and compare integers as primitive operations. They asked whether their current bound on the number of registers for multiplying and dividing fast (running in time linear in the size of the input) can be improved and whether one can output fast the powers of two summing up to a positive integer in subquadratic time. Both questions are answered positively. Furthermore, it is shown that every function computed by only one register is automatic and that automatic functions with one input can be computed with four registers in linear time; automatic functions with a larger number of inputs can be computed with 5 registers in linear time. There is a nonautomatic function with one input which can be computed with two registers in linear time.

Recommendations

• Addition Machines
• A computation model with automatic functions and relations as primitive operations
• Computations on register machines with counters
• Performance analysis of ``addition machines
• Register machines with counters

Cites work

• A computation model with automatic functions and relations as primitive operations
• Addition Machines
• Algebraic Complexity Theory
• Algorithms
• Automata Presenting Structures: A Survey of the Finite String Case
• Automatic functions, linear time and learning
• Automatic structures: twenty years later
• Division in idealized unit cost RAMs
• Fast direct computation of modular reduction
• Fibonacci linear forms and parallel arithmetic algorithms for large numbers
• Finite presentations of infinite structures: Automata and interpretations
• scientific article; zbMATH DE number 3841819 (Why is no real title available?)
• scientific article; zbMATH DE number 3637287 (Why is no real title available?)
• scientific article; zbMATH DE number 1499098 (Why is no real title available?)
• scientific article; zbMATH DE number 3397597 (Why is no real title available?)
• Integer multiplication in time \(O(n\log n)\)
• Introduction to algorithms.
• On the base-dependence of sets of numbers recognizable by finite automata
• Presburgerness of predicates regular in two number systems
• Primality and identity testing via Chinese remaindering
• Semiautomatic structures
• Three lectures on automatic structures
• Trusted computing with addition machines. I
• Trusted computing with addition machines. II
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(3)

• Additive number theory via automata theory
• A computation model with automatic functions and relations as primitive operations
• Addition Machines

This page was built for publication: Addition machines, automatic functions and open problems of Floyd and Knuth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6098150)