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.
This paper surveys some results involving bounded query classes in the context of structural and descriptive complexity theory, and reviews concrete complete problems in AI and modal logic.
In this paper an overview on proof systems for structured algebraic specifications is presented. As underlying language we choose an ASL-like kernel language which includes reachability and observability operators. Three different kinds of proof systems are studied. The first two approaches are non-compositional systems where the basic idea is to compute for any structured specification a flat unstructured...
We will demonstrate how to use Kolmogorov complexity to do the average-case analysis via some examples. These examples include: longest common subsequence problem and shortest common supersequence problem [9, 11], problems in computational geometry [14], average case analysis of Heapsort [19, 17], average nni-distance between two binary rooted leave-labeled trees [23], compact routing in computer...
This paper is an extended and modified version of [10]. A protocol with local rules is presented for enumerating anonymous nodes of finite graphs. It is proved that such algorithms do not exists for the class of ambiguous graphs, defined in the paper; the proposed algorithm works successfully for remaining non-ambiguous graphs. It is also proved that protocol is fair, which means that no enumeration...
By concatenating linear-time codes with small, good codes, it is possible to construct in polynomial time a family of asymptotically good codes that approach the Shannon bound that can be encoded and decoded in linear time. Moreover, their probability of decoder error is exponentially small in the block length of the codes. In this survey, we will explain exactly what this statement means, how it...
Research in theoretical computer science has focused in the past mainly on static computation problems. In a static computation the input is known before the start of the computation and the goal is to minimize the number of steps till termination with a correct output. Many important processes in today's computing are dynamic processes, whereby input is continuously injected to the system, and the...
We present sorting algorithms on the recently introduced multi-mesh, a network consisting of n2 meshes of size n x n which are connected by the free marginal links of the meshes. Our algorithm takes 41n + o(n) steps which is a significant improvement to previously known algorithms. The sorting algorithm is based on a technique using interchange of data between the n x n submeshes to distribute...
We introduce a subclass of Valk's self-modifying nets. The considered nets appear as stratified sums of ordinary nets and they arise as a counterpart to cascade products of automata via the duality between automata and nets based on regions in automata. Nets in this class, called stratified nets, cannot exhibit circular dependences between places: inscriptions on flow arcs attached to a given place,...
A very simple randomised distributed algorithm imposing an acyclic orientation on any arbitrary anonymous asynchronous network is presented in this paper. The problem is faced under the noinfo assumption: no network attribute is available and when the algorithm starts each processor only knows the number of its input/output ports (i.e. the number of its immediate neighbours). The presented algorithm...
The family of rational subsets of a direct product of free monoids Σ 1* × ... × Σ n* (the rational relations) is not closed under Boolean operations, except when n = 1 or when all Σi's are empty or singletons. In this paper we introduce the family of generalized rational subsets of an arbitrary monoid as the closure of the singletons under the Boolean operations, concatenation...
We consider the problem of broadcasting in the presence of linearly bounded number of transient faults. For some fixed 0 < α < 1 we assume that at most ai faulty transmissions can occur during the first i time units of the broadcasting algorithm execution, for every natural i. In a unit of time every node can communicate with at most one neighbor. We prove that some bounded degree networks are...
We study real number complexity classes under a logical point of view. Following the approaches by Blum, Shub, and Smale [3] for computability and by Grädel and Meer [10] for descriptive complexity theory over the reals, we characterize such complexity classes by purely logical means. Among them we mainly find parallel classes which have not been studied in [10].
Collage grammars generate picture languages in a context-free way. The generating process is based on the replacement of atomic nonterminal items and can be seen as an adaptation of the notion of hyperedge replacement known from the area of context-free graph generation. While a pumping lemma holds for hyperedge replacement graph grammars and is quite useful to show that certain graph languages cannot...
We obtain a formula for the subword complexity of every binary DOL word which is a fixed point of a uniform morphism, i.e. a morphism in which the images of all letters have the same length. We establish that the complexity function can be found from its values for little lengths and some simple parameters of the morphism. The property of circularity is important for the view of the formula. In general...
In this paper we show two results on PRAM with constant fraction of memory faults. First we show how to preprocess (i.e. connect a constant fraction of processors into a binary tree) a faulty EREW PRAM with n/log n processors and O(n) memory cells in O(log n) time. The preprocessing is a basic step of simulations from [7, 9, 17]. Our algorithm, together with the results from [17], gives a first fully...
We will study systems for which a maximal number of concurrently executing (time consuming) actions is statically fixed. Two possible mechanisms of executions of actions are studied. Either the executions can be interrupted or they cannot. In the former case we show that equivalent processes remain equivalent when the number of resources (processors) which they have at disposal is changed. In the...
A watchman route in a polygon P is a route inside P such that each point in the interior of P is visible from at least one point along the route. The objective of the shortest watchman route problem is to minimize the length of the watchman route for a given polygon. In 1991 Chin and Ntafos claimed an O(n4) algorithm, solving the shortest watchman route problem for simple polygons, given...
The study of query order was initiated by Hemaspaandra, Hempel, and Wechsung [HHW]. Their goal was to learn whether the order of access to information sources affects the class of problems that can be solved. They showed that in the boolean hierarchy over NP, order matters. In the present paper, we study the power of query order when accessing levels of the polynomial hierarchy, and we show that here...
We investigate the power of polynomial time machines whose acceptance mechanism is defined by a word problem over some finite semigroup, monoid, or group. For the case of non-solvable groups or monoids (semigroups, resp.) containing non-solvable groups it follows from [21] that the according complexity class is PSPACE. For solvable monoids it was shown there that the according class is always a subclass...
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.