On the algorithmic complexity of some numeration-related problems

DOI10.5486/PMD.2021.8758MaRDI QIDQ5859586zbMATH OpenOpenAlexFDO

Authors Dávid Bóka, Péter Burcsi, János M. Uray

Publication date 16 April 2021

Published in Publicationes Mathematicae Debrecen (Search for Journal in Brave)

Full work available at URL https://doi.org/10.5486/pmd.2021.8758

zbMATH Keywords

algorithmic complexityexpansive polynomialsgeneralized number systemnumeration system

Mathematics Subject Classification ID

Radix representation; digital problems (11A63) Matrices, determinants in number theory (11C20) Randomized algorithms (68W20) Symbolic computation and algebraic computation (68W30)

Recommendations

• Numeration systems: a link between number theory and formal language theory
• On-line finite automata for addition in some numeration systems
• scientific article; zbMATH DE number 3931097
• On the computational complexity of algebraic numbers: the Hartmanis-Stearns problem revisited
• Minimal digit sets for parallel addition in non-standard numeration systems

Cited in

(6)

• Algorithmic complexity of the problem of occurrence in commutants and members of the lower central series
• On the complexity of algebraic numbers
• Polynomial Time Algorithms for Finding Integer Relations among Real Numbers
• scientific article; zbMATH DE number 3961588 (Why is no real title available?)
• scientific article; zbMATH DE number 6146470 (Why is no real title available?)
• An improved exact algorithm for the domatic number problem

This page was built for publication: On the algorithmic complexity of some numeration-related problems

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