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 results that we have presented should serve a as a warning: reducing a problem in complexity theory to a communication game may be only a first small step towards the solution, however intuitively clear the game may look like. Still, if we do not look just for record lower bounds, these reductions may often be, in a sense, very rewarding, as they lead to nice mathematical problems and show connections...
Valuations — morphisms from (Σ*·λ) to ((0, ∞),·,1) —are a simple generalization of Bernoulli morphisms (distributions, measures) as introduced in [12, 20, 6, 4, 5, 21]. This paper shows that valuations are not only useful within the theory of codes, but also when dealing with ambiguity, especially in regular expressions and contextfree grammars, or for defining outer measures on the space...
This paper deals with finite size recurrent neural networks which consist of general (possibly cyclic) interconnections of evolving processors. Each neuron may assume a real activation value in a bounded range. We provide the first rigorous foundations for recurrent networks which are built of probabilistic unreliable analog devices and present randomness in their update. The first model we...
This paper investigates automated model checking possibilities for CTL* formulae over infinite transition systems represented by relational automata (RA). The general model checking problem for CTL* formulae over RA is shown undecidable, the undecidability being observed already on the class of Restricted CTL formulae. The decidability result, however, is obtained for another substantial subset of...
We introduce a formal framework to study the time and space complexity of computing with faulty memory. For the fault-free case, time and space complexities were studied using the “pebbling game” model. We extend this model to the faulty case, where the content of memory cells may be erased. The model captures notions such as “check points” (keeping multiple copies of intermediate results), and “recovery”...
In this paper we define a precise notion of abstraction relation between continuous dynamical systems and discrete state-transition systems. Our main result states that every Turing Machine can be realized by a dynamical system with piecewise-constant derivatives in a 3-dimensional space and thus the reachability problem for such systems is undecidable for 3 dimensions. A decision procedure for 2-dimensional...
Multi-pebble automata are considered, appropriately restricted to accept only regular languages, and enriched with additional features, such as nondeterminism and concurrency. We investigate the succinctness of such machines, and the extent to which this succinctness carries over to make the reasoning problem in propositional dynamic logic (PDL) more difficult. The two main results establish that...
Core-ML is a basic subset of most functional programming languages. It consists of the simply typed (or monomorphic) λ-calculus, simply typed equality over atomic constants, and let as the only polymorphic construct. We present a synthesis of recent results which characterize this “toy” language's expressive power as well as its type reconstruction (or type inference) problem. More specifically: (1)...
Recently, Abiteboul and Kanellakis introduced the notion of determinate query to describe database queries having the ability to create new domain elements. As there are no natural determinate-complete query languages known, more restrictive (the constructive queries) and more general (the semideterministic queries) notions of query were considered. Here, we show that the advantage of the second approach...
In this paper, a global function is a function that computes a (local) function in each ordered structure of a specified vocabulary. We design algebras of global functions for a number of complexity classes for which such algebras have not been known, e.g. for the functions computable in nondeterministic logarithmic space, or in nondeterministic polynomial time. In addition, we present a functional...
An asynchronous automaton consists of a set of processes that cooperate in processing letters of the input. Each letter read prompts some of the processes to synchronize and decide on a joint move according to a non-deterministic transition relation. Zielonka's theorem tells us that these automata can be determinized while retaining the synchronization structure. Unfortunately, this construction...
We present a subset automaton construction for asynchronous cellular automata. This provides an answer to the problem of direct determinization for asynchronous cellular automata for finite traces, which has been open for several years. We use the subset automaton construction in order to extend Klarlund's progress measure technique of complementation to non-deterministic asynchronous cellular Büchi...
A new semantics for process description languages that discriminates according to the distribution in space of processes is proposed. The semantics is based on a set of distributed transition rules that record spatial information and on a notion of equivalence that discriminates according to which actions processes can perform and where these actions are performed. The new semantics is proven to coincide...
We present a coordinated pair of general labeled transition system models for describing timed and untimed concurrent systems. Both of the models incorporate liveness properties as well as safety properties. The models are related via an embedding of the untimed model into the timed model, which preserves all the interesting attributes of the untimed model. Both models include notions of environment-freedom...
We analyze the average behaviour under the bst probability model of the simplest and most commonly used sequential tree-matching algorithm. When the uniform probability model for the input is assumed, it is well known that it takes O(n) steps on average to search all occurrences of a random pattern P in a random text T of joint size n. Under the bst probability model the analysis is itself more complex,...
Finding shortest common supersequences (SCS) and longest common subsequences (LCS) for a given set of sequences are two well-known NP-hard problems. They have important applications in many areas including computational molecular biology (e.g., sequence alignment), data compression, planning, text editing (e.g., diff function in UNIX), etc. [1, 6, 7, 8, 10, 17, 19, 22, 23, 24, 26, 27]. The question...
The Prefix Matching Problem is to determine, for each location in the text t, the longest prefix of a given pattern p which occurs beginning at that location. We present two work-optimal parallel algorithms for this problem. The first algorithm works for the case when the characters in p and t are drawn from an alphabet set of size polynomial in m + n, where m = ¦p¦ and n = ¦t¦; it takes O(log m)...
Recent proliferation of digitized data and the expected unprecedented growth in the volume of stored and transmitted data motivated the definition of the compressed matching paradigm. This is the problem of efficiently finding a pattern P in a compressed text T without the need to decompress. We present the first optimal two-dimensional compressed matching algorithm. The compression under consideration...
Given a graph G with m edges and n nodes, a spanning tree T of G, and an edge e that is being deleted from or inserted into G, we give efficient O(n) algorithms to compute a possible swap for e that minimizes the diameter of the new spanning tree. This problem arises in high-speed networks, particularly in optical networks.
A hash table is a representation of a set in a linear size data structure that supports constant-time membership queries. We show how to construct a hash table for any given set of n keys in O(lg lg n) parallel time with high probability, using n processors on a weak version of a crcw pram. The algorithm is simple and is sketched by the following: 1. Partition the input set into buckets by...
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.