Abstract Our previous research showed that the semantic tableau deductive methodology of Fitting and Smullyan permits boundary-case exceptions to the second incompleteness theorem, if multiplication is viewed as a 3-way relation (rather than as a total function). It is known that tableau methodologies prove a schema of theorems verifying all instances of the law of the excluded middle. But if one promotes this schema of theorems into formalized logical axioms, then the meaning of the pronoun of ‘I’, used by our self-referencing engine, changes quite sharply. Our partial evasions of the second incompleteness theorem shall then come to a complete halt.

Abstract Gödel's Second Incompleteness Theorem states axiom systems of sufficient strength are unable to verify their own consistency. We will show that axiomatizations for a computer's floating point arithmetic can recognize their cut-free consistency in a stronger respect than is feasible under integer arithmetics. This paper will include both new generalizations of the Second Incompleteness Theorem and techniques for evading it.

Abstract This article will study a class of deduction systems that allow for a limited use of the modus ponens method of deduction. We will show that it is possible to devise axiom systems α that can recognize their consistency under a deduction systemD provided that: (1) α treats multiplication as a 3-way relation (rather than as a total function), and that (2)Ddoes not allow for the use of a modus ponens methodology above essentially the levels of Π1and Σ1formulae. Part of what will make this boundary-case exception to the Second Incompleteness Theorem interesting is that we will also characterize generalizations of the Second Incompleteness Theorem that take force when we only slightly weaken the assumptions of our boundary-case exceptions in any of several further directions.

Abstract Let us recall that Raphael Robinson's Arithmetic Q is an axiom system that differs from Peano Arithmetic essentially by containing no Induction axioms [13], [18]. We will generalize the semantic-tableaux version of the Second Incompleteness Theorem almost to the level of System Q. We will prove that there exists a single rather long Π1 sentence, valid in the standard model of the Natural Numbers and denoted as V. such that if α is any finite consistent extension of Q + V then α will be unable to prove its Semantic Tableaux consistency. The same result will also apply to axiom systems α with infinite cardinality when these infinite-sized axiom systems satisfy a minor additional constraint, called the Conventional Encoding Property. Our formalism will also imply that the semantic-tableaux version of the Second Incompleteness Theorem generalizes for the axiom system IΣ0, as well as for all its natural extensions. (This answers an open question raised twenty years ago by Paris and Wilkie [15].)

Abstract We will study several weak axiom systems that use the Subtraction and Division primitives (rather than Addition and Multiplication) to formally encode the theorems of Arithmetic. Provided such axiom systems do not recognize Multiplication as a total function, we will show that it is feasible for them to verify their Semantic Tableaux, Herbrand, and Cut-Free consistencies. If our axiom systems additionally do not recognize Addition as a total function, they will be capable of recognizing the consistency of their Hilbert-style deductive proofs. Our axiom systems will not be strong enough to recognize their Canonical Reflection principle, but they will be capable of recognizing an approximation of it, called the “Tangibility Reflection Principle”. We will also prove some new versions of the Second Incompleteness Theorem stating essentially that it is not possible to extend our exceptions to the Incompleteness Theorem much further.

This article illustrates several examples of computer science problems whose performance can be improved with the use of either the fusion trees [Fredman and Willard, J. Comput. System Sci., 47 (1993), pp. 424--436; Fredman and Willard, J. Comput. System Sci., 48 (1994), pp. 533--551] or one of several recent improvements to this data structure. It is likely that many other data structures can also have their performance improved with fusion trees. The examples here are only illustrative.

In many computing applications, there are several equivalent algorithms capable of performing a particular task, and no one is the most efficient under all statistical distributions of the data. In such contexts, a good heuristic is to take a sample of the database and use it to guess which procedure is likely to be the most efficient. This paper defines the very general notion of a differentiable query problem and shows that the ideal sample size for guessing the optimal choice of algorithm is O ( N 2/3 ) for all differential problems involving approximately N executing steps.

The fusion tree method is extended to develop a linear-time algorithm for the minimum spanning tree problem and an O(m+n log n/log log n) implementation of Dijkstra's shortest-path algorithm for a graph with n vertices and m edges. The shortest-path algorithm surpasses information-theoretic limitations. The extension of the fusion tree method involves the development of a new data structure, the atomic heap. The atomic heap accommodates heap (priority queue) operations in constant amortized time under suitable polylog restrictions on the heap size. The linear-time minimum spanning tree algorithm results from a direct application of the atomic heap. To obtain the shortest path algorithm, the atomic heap is used as a building block to construct a new data structure, the AF-heap, which has no size restrictions and surpasses information theoretic limitations. The AF-heap belongs to the Fibonacci heap family.>

Throughout this paper q will denote a query such that I is the number of tuples inputted into the query, and U is the number of tuples in its output. We will say that q has quasi-linear complexity iff for some constant d, it is executable in time O(U + I logdI) and space O(I + U). This article will define a large subset of the relational calculus, called RCS, and show that all RCS queries are executable by quasi-linear algorithms.

Article Free Access Share on BLASTING through the information theoretic barrier with FUSION TREES Authors: M. L. Fredman Rutgers, Bellcore and UCSD Rutgers, Bellcore and UCSDView Profile , D. E. Willard SUNY at Albany SUNY at AlbanyView Profile Authors Info & Claims STOC '90: Proceedings of the twenty-second annual ACM symposium on Theory of ComputingApril 1990 Pages 1–7https://doi.org/10.1145/100216.100217Published:01 April 1990Publication History 35citation1,119DownloadsMetricsTotal Citations35Total Downloads1,119Last 12 Months86Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We define a new formalism called the quasi-valid range aggregation. This formalism leads to a new and quite simple method for reducing non-range query-like problems to range queries and often to orthogonal range queries, with immediate applications to the ATTRACTED NEIGHBOR and the planar ALL-PAIRS NEAREST NEIGHBORS problems (the latter being solved optimally on both parallel and sequential machines). A point of special interest is that our new formalism permits operators “+” that are neither associative nor abelian (unlike traditional range query theory). The technique described in this paper should therefore have significant other applications besides those we consider, especially in the context of parallel computational geometry.

An orthogonal query that asks to aggregate the set of records in k -dimensional box regions is studied, and it is shown that space O ( N ((log N )/(log log N )) k -1 ) makes possible a combined time complexity O (log k N ) for retrievals, insertions, and deletions.

We propose a new search technique, called the Shear-Based Format, which shows that Yao's lower bound on the time-space tradeoff for orthogonal range queries is either optimal or nearly optimal [Ya82, Ya85]. Shearing is also a very pragmatic technique.

We propose two selection protols that run on multiple access channels in log-logarithmic expected time, and establish a complementary lower bound showing that the first protocols falls within an additive constant of optimality and that the second differs from optimality by less than any multiplicative factor infinitesimally greater than 1 as the size of the problem approaches infinity. It is difficult to second-guess the fast-changing electronics industry, but our mathematical analysis could be relevant outside the traditional interests of communications protocols to semaphore-like problems.

In dynamic storage allocation, successive allocation and freeing of blocks normally leads to fragmentation of storage.When a new block is to.beallocated, fragmentation may prevent any single region of available storage from being large enough for the new block, even though the total amount of available space is sufftcient.When such a conflict arises, dynamic storage allocation systems typically require time-consuming garbage collection or they simply break down.This paper investigates strategies for maintaining storage that allow allocation of blocks to proceed in spite of fragmentation conflicts, at the cost of moving some blocks already allocated are investigated.Such a scheme is reasonable only if it can be guaranteed that the cost of moving blocks never becomes too large relative to the size of the.block to be allocated.Two such schemes are described.They are similar to the buddy system in that they always align the left end of a block of size n at a position that is a multiple of 2"005"'.The schemes differ in the criterion for choosing an interval to free up when no interval of the right size is empty: the Not Full (NF) scheme chooses an interval that is not full, while the Not Too Full (NTF) scheme chooses an interval that is at most as full as all of memory.Tight worst-case bounds are obtained for these schemes as a function of the proportion of memory tilled.The results show that the worst-case cost for NF, the simpler of the two schemes, can be much worse than that for NTF when memory is not too full.However, simulations suggest that the average cost may be much less than the worst-case.cost.

A database is said to allow range restrictions if one may request that only records with some specified field in a specified range be considered when answering a given query. A transformation is presented that enables range restrictions to be added to an arbitrary dynamic data structure on n elements, provided that the problem satisfies a certain decomposability condition and that one is willing to allow increases by a factor of O (log n ) in the worst-case time for an operation and in the space used. This is a generalization of a known transformation that works for static structures. This transformation is then used to produce a data structure for range queries in k dimensions with worst-case times of O (log k n ) for each insertion, deletion, or query operation.

Consider a set of N records corresponding to points in k-dimensional space ($k \geqq 2$). This article introduces one new data structure which uses memory $O(N\log ^{k - 1} N)$ for supporting orthogonal range queries with worst-case complexity $O(\log ^{k - 1} N)$ and several modifications of this proposal for a dynamic environment. These results are especially useful when $k = 2$.

The first algorithm that searches unindexed and nonuniformly distributed ordered files in $\log \log N$ expected time is presented in this paper. Our analysis rests on a synthesis of concepts from the literature on interpolation search and on the method of regula falsi in numerical analysis.

In this paper we define a language based on a broad subset of the relational calculus and show all expressions in this language can be evaluated in space O(N) and time O(N logdN), where d is a small constant whose value depends on the particular predicate and where N is the number of records stored in the data base. We currently have no hard statistics, but a reasonable guess seems to be that a standard sequential random access machine can handle 95% or more of commercial requests in time O(N log N) and memory O(N) using this technique.

We propose two protocols for resolving conflicts on ethernetlike mediums in log-logarithmicexpected time and prove our algorithms are optimal up to an additive constant.It is difficult to second-guess the fast-changing electronics industry, but our analysis could be relevant outside the traditional interests of the ethernet literature to semaphore-like problems.

In this article, we study an alternate approach that shifts the records among adjacent pages rather than using overflow pointers when space is needed for inserting a record in a sequential file. We show how to use this method to achieve a worst-case record insertion-deletion complexity of O[(log2N)/(D-d)] page-accesses, in (d-D)-dense files.

Given a set of N points on the plane and an arbitrary polygon, we consider how to efficiently find the subset of these points lying inside this polygon. A data structure will be displayed that occupies $O(N)$ space and enables polygon retrieval to be performed in $O(N^{\log _6 4} )$ worst-case execution time. This is the best currently known worst-case complexity.