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.
Much complexity-theoretic work on parallelism has focused on the class NC, which is defined in terms of logspace-uniform circuits. Yet P-uniform circuit complexity is in some ways a more natural setting for studying feasible parallelism. In this paper, P-uniform NC (PUNC) is characterized in terms of space-bounded AuxPDA's and alternating Turing Machines with bounded access to the input. We also present...
In this paper we compare the performances of concurrency control algorithms using the combinatorics of words. We characterize such control algorithms by a triple of values, respectively estimating the frequency of accepted executions of concurrent transactions, the degree of authorized parallelism, and the load factor (a value related to the average number of elementary operations needed for the serialization...
In view of the results of Theorems III.1 and Theorem III.2, all the minimal bilinear algorithms for computing the coefficients of R(u)S(u) mod Q(u)l have multiplications of the form R(αj)S(αj) hence the algorithm requires large coefficients (as in l=1). Therefore using the identity R(u)S(u)=R(u)S(u) mod P(u) where degP(u)=2n − 1 with distinct irreducible,...
This paper proves a tradeoff between the time it takes to search for elements in an implicit dictionary and the time it takes to update the value of elements in specified locations of the dictionary. It essentially shows that if the update time is constant, then the search time is ω(nɛ) for some constant ɛ>0.
What do a pushdown and a queue have in common? What is their intersection? Is it a counter? If we add the one-reversal restriction, is a one-reversal counter exactly the intersection of a one-reversal pushdown and a queue or, symmetrically, the intersection of a one-reset tape and a pushdown? These and similar assumptions can be heard here and there, and there are some conjectures by Autebert et al...
Ternary simulation techniques provide efficient methods for the analysis of the behavior of VLSI circuits. However, the results of ternary simulation have not been completely characterized. In this paper we outline the proof of the Brzozowski-Yoeli conjecture (stated in 1976) that the results of the ternary simulation of a gate network N correspond to the results of the binary race analysis of Ñ in...
Rational functions of a free monoid A* into the free cyclic monoid t* generated by a unique element t, can be viewed as assigning an integer to every word u∈A*. We investigate those functions which count occurrences of some fixed (and special) subsets $$X \subseteq A^ *$$ in all words of A* and show that they can be characterized in terms of "bounded variation", a notion which is...
We identify and study a frequently occurring subclass of Concurrent-Read, Exclusive-Write Parallel Random Access Machines (CREW-PRAM's). Called Concurrent-Read, Owner -Write, or CROW-PRAM's, these are machines in which each global memory location is assigned a unique “owner” processor, which is the only processor allowed to write into it. Most known CREW-PRAM algorithms are in fact CROW-PRAM algorithms...
This paper develops techniques for studying complexity classes that are not covered by known recursive enumerations of machines. Often, counting classes, probabilistic classes, and intersection classes lack such enumerations. Concentrating on the counting class UP, we show that there are relativizations for which UPA has no complete languages and other relativizations for which P ...
The well-known Knuth-Bendix completion algorithm which computes a confluent and finitely terminating term rewriting system from a given set of equations, can either terminate with success or abort or even nonterminate. Very little is known about the origin of nontermination of this algorithm. We study the structural properties of rewrite rules which cause nontermination. The notion of the crossed...
The alternating machine having a separate input tape with k two-way, read-only heads, and a certain number of internal configurations — AM(k) is considered as a parallel computing model. For the complexity measure TIME·SPACE·PARALLELISM (TSP), the optimal lower bounds ω(n2) and ω (n3/2) resp. are proved for the recognition of specific languages on AM (1), and AM(k) respectively. For the complexity...
Rational relations (finite transductions) which are equivalence relations are discussed. After establishing a containment hierarchy, the complexity of canonical function computation and a number of class membership decision problems are studied. The following classes are considered: (1) Rational Equivalence Relations, (2) Equivalence Kernels of Rational Functions, (3) Deterministic...
In the conclusion of [HM2] Halpern and Moses expressed their interest in a logical system in which one could talk about knowledge and belief (and belief about knowledge, knowledge about belief and so on). We investigate such systems. In the first part of the paper knowledge and belief, without time, are considered. Common knowledge and common belief are defined and compared. A logical system and a...
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.