The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
The evolution of certain pointer-based implementations of dictionaries, linear lists and priority queues is studied. Under the assumption of equiprobability of histories, i.e., of paths through the internal state space of the implementation, the n → ∞ asymptotics of the space and time costs of a sequence of n supported operations are computed. For list implementations the mean integrated spatial...
Formal aspects of approximated solutions to difficult problems are considered. We define an approximation machine and its language as a formal model of computation. We strengthen previous results by showing the interpretation of the complexity classes with density in terms of approximation languages. In particular, we analyze the worst-case, the best-case and the average-case complexity related to...
In this paper the introductory concepts and chosen applications of the Calculus of Self-modifiable Algorithms (CSA) are presented. The CSA model is a theory for describing parallel behavior. In contrast to the well-known Hoare's CSP and Milner's CCS parallel computing theories, the CSA model was designed as a theory within Artificial Intelligence. It considers self-modifiable algorithms which are...
We show that the complexity-theoretic notion of almost-everywhere complex functions is identical to the recursion-theoretic notion of bi-immune sets in the nondeterministic space domain. Furthermore we derive a very strong separation theorem for nondeterministic space — witnessing this fact by almost-everywhere complex sets — that is equivalent to the traditional infinitely-often complex hierarchy...
Deterministic Prediction in progressive coding of images is investigated. Progressive coding first creates a sequence of resolution layers by beginning with an original image and reducing its resolution several times by factors of two. Next, the resultant layers are losslessly encoded. The lowest-resolution layer is encoded first, then each higher resolution image is built incrementally...
We analyze the implementation of set operations using binary tries. Our techniques are substantially simpler than previous techniques used for this problem, and allow us to analysis not only the expected performance but also the probability distribution of the performance. We show that by making use of constant-time equality tests, we can achieve better performance than any previously known method...
Although classifiation is perhaps the oldest practical application of MML inference, the early algorithm was subject to weakly inconsistent estimation. The same problem is inherent in any MML inference which infers many discrete "nuisance" parameters. A solution has been found using a novel coding trick, which could be useful in many inductive inferences.
Semi-unification is a generalization of both unification and matching with applications in proof theory, term rewriting systems, polymorphic type inference, and natural language processing. It is the problem of solving a set of term inequalities M1 ≤ N1, ..., Mk <- Nk, where ≤ is interpreted as the subsumption...
Yamamoto and Noguchi [YN87] raised the question of whether every recursively enumberable set can be accepted by a 1-tape or off-line 1-tape alternating Turing machine (ATM) whose (work)tape head makes only a constant number of reversals. In this paper, we answer the open question in the negative. We show that (1) constant-reversal 1-tape ATM's accept only regular languages and (2) there exists a recursive...
Levcopolous and Overmars [12] describe a search tree in which the time to insert or delete a key is O(1) once the position of the key to be inserted or deleted was known. Their data structure does not support fingers, pointers to points of high access or update activity in the set such that access and update operations in the vicinity of a finger are particularly efficient [3, 8, 10, 11, 15]. Levcopolous...
We use matrix recurrences to analyze the expected behaviour of algorithms on trees. We apply this technique to the average case analysis of balanced search trees and digital trees. In particular we give the exact solution for a fringe analysis problem, a technique used for search trees, that was unknown before. This method also makes easier to solve some scalar recurrences.
We consider the problem of finding elements in tableau-defined monoids. The solution of this problem is important to the minimization of restricted relational database queries. Although the problem has been shown to be NP-complete in general, many polynomial-time algorithms have been proposed for some subclasses of the general problem. The contribution of this paper is a new algorithm that finds elements...
We describe an ongoing project, to develop a general theory of computation and specification over classes of structures, modelling abstract data types. Applications include logic programming module development and hardware design for synchronous concurrent algorithms.
In this paper, we define the language (FO + posHP), where HP is the Hamiltonian path operator, and show that a problem can be represented by a sentence of this language if and only if the problem is in NP. We also show that every sentence of this language can be written in a normal form, and so establish the fact that the problem of deciding whether there is a directed Hamiltonian path between two...
Joseph and Young [JY-85] hypothesized that the Berman-Hartmanis isomorphism conjecture fails if there exists a k-completely creative set in NP with no p-invertible p-completely productive functions. We verify this hypothesis for DEXT based on new results of p-creative sets in [Wan-89]. In particular, we prove that the isomorphism conjecture for DEXT fails iff there is a p-creative set for P in DEXT...
The concepts of wait-freedom and low-atomicity in concurrent shared-variable programs are explored in the frameworks of temporal logic and UNITY. With the help of some new primitives, axioms for these concepts are presented. Later, these axioms are used to prove the impossibility of distributed consensus.
In this paper we investigate the way in which the Gamma model, proposed by Banâtre and Le Metayer [1], might be supported in a functional language. We discuss the mechanism behind the model and examine the difficulties which arise when implementing Gamma in a functional language. We also explore its applicability as a programming paradigm by developing a library of higher order functions which can...
Certain real life binary relations are symmetric (map point connections, “iff” mathematical statements, multiprocessor links). Such relations can be represented by symmetric 0–1 matrices. Algorithms which take advantage of the symmetry when acting on such matrices, are more efficient than algorithms that are “good for all cases” by assuming a generic (non-symmetric) matrix. No algorithm, to our knowledge,...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.