On the limits of computations with the floor function

DOI10.1016/0890-5401(88)90031-4MaRDI QIDQ1112603zbMATH OpenOpenAlexFDO

Authors Bettina Just, Friedhelm Meyer auf der Heide, László Babai

Publication date 1988

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0890-5401(88)90031-4

zbMATH Keywords

algebraic computation treesanalytic computation treeanalytic functionsdecidable languagesfloor functionhaltingmeasurable setsreal function

Mathematics Subject Classification ID

Real-analytic functions (26E05) Classes of sets (Borel fields, (sigma)-rings, etc.), measurable sets, Suslin sets, analytic sets (28A05) Topology of special sets defined by functions (54C50) Algorithms in computer science (68W99)

Review text

The authors define the concept of an ``analytic computation tree (ACT) as an algorithmic model (decision tree) which operates on \({\mathbb{R}}^ n\) and at each step either (a) compares a real number with 0 and branches according to the result, or (b) computes a real function which is a composition of analytic functions and the floor function. ACTs appear thus as a direct generalization of the ``algebraic computation trees introduced by \textit{M. Ben-Or} [Proc. 15th Ann. ACM Symp. Theory Comput., 80-86 (1983)]. Topological arguments are used in an attempt to characterize those languages (subsets of \({\mathbb{R}}^ n)\) which are decidable by ACTs. Necessary conditions for a language to be accepted (or accepted by halting) by an ACT are derived; these are expressed in terms of zero sets with open complements or in terms of Lebesgue or Jordan measurable sets. As an application of these results, it is shown that the languages \({\mathbb{Q}}^ n\), REL (the \({\mathbb{Z}}\)-linearly dependent n-tuples of reals), and ALG (the algebraically dependent n-tuples) are accepted (but not their complements in \({\mathbb{R}}^ n)\).

Recommendations

• Lower Bounds for Computations with the Floor Operation
• scientific article; zbMATH DE number 4117838
• Curious bounds for floor function sums
• Computability of Fraïssé limits
• On the computation of limsups
• The function \(\lfloor a/m\rfloor\) in sharply bounded arithmetic
• scientific article; zbMATH DE number 2085171
• The limits of fixed-order computation
• The Computational Complexity of Continued Fractions
• On the problem of computing the values of \(L\)-functions

Cites work

• A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem
• A lower time bound for the knapsack problem on random access machines
• Approximation to bounded holomorphic functions on strictly pseudoconvex domains
• scientific article; zbMATH DE number 3980478 (Why is no real title available?)
• Lower bounds for solving linear diophantine equations on random access machines
• Lower time bounds for integer programming with two variables

Cited in

(9)

• On the hardness of approximating shortest integer relations among rational numbers
• Simulating probabilistic by deterministic algebraic computation trees
• Fast exponentiation using the truncation operation
• scientific article; zbMATH DE number 4072374 (Why is no real title available?)
• On computations with integer division
• The PSLQ algorithm for empirical data
• scientific article; zbMATH DE number 4117838 (Why is no real title available?)
• On genuinely time bounded computations
• Rational approximations, multidimensional continued fractions, and lattice reduction

This page was built for publication: On the limits of computations with the floor function

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