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.
A mathematical model is presented which enables to give a meaningful interpretation to the assertion "with a probability greater than 1-ɛ the finite sequence of letters under consideration is an initial segment of a relatively simple infinite recursive sequence" and to give an at least potential possibility how to test the validity of such an assertion. The model is based on a modified version...
The complexity of languages generated by context-free grammars with disconnecting is investigated. It is shown that even linear and deterministic context-free languages can generate languages of multisets, the membership problem of which is NP-complete. In contrast to that, this problem is in DSPACE(log n) for regular sets.
We present a new model of parallel computation called the "array processing machine" or APM. The APM was designed to closely model the architecture of existing vector- and array processors, and to provide a suitable unifying framework for the complexity theory of parallel combinatorial and numerical algorithms.
During the fabrication of masks for integrated circuits, the polygons on the pattern generator must be covered by a preferably as small as possible number of rectangles. In this paper we present a fast and simple heuristic, based on Voronoi diagrams, which covers arbitrary polygons without acute interior angles by rectangles in time O(nlogn + r), where n is the number of edges of the polygon and r...
Using a compact metric space, we study the continuity properties of the subset transformation associated to a logic program. We show that this transformation is ω-continuous for the lower Scott topology on the set of closed subsets of this space. We also show a greatest fixpoint and a least fixpoint theorem, and give a proof-theoretic characterization of the least fixpoint.
An interpretation of lower bounds proofs as proofs of lower bounds on the universal circuits is presented. This interpretation is displayed on representative proof samples from [1,3,7 – 10]. It enables one to explain the difficulty of proving lower bounds and to forecast possibilities of proving high lower bounds for arbitrary computational model.
A finite group G is commonly presented by a set of elements which generate G. We argue that for algorithmic purposes a considerably better presentation for a fixed group G is given by random generator set for G: a set of random elements which generate G. We bound the expected number of random elements requied to generate a given group G. Our main results are probabilistic algorithms which take...
Let VASS(k,l,n) denote the class of k-dimensional n-state Vector Addition Systems with States, where the largest integer mentioned, in an instance, can be represented in l bits. Using a modification of the technique used by Rackoff, we show that the Boundedness Problem (BP), for VASS(k,l,n), can be solved in O((l+log n)*2c*k*log k) nondeterministic space. By modifying Lipton's result, a lower bound...
We considerer the families of languages produced by two-way transducers, and prove iteration lemmas for them. Thus it is shown that the Dyck language D′ 1* doesn't belong to the deterministic family, and consequently that the Dyck language D′ 2* doesn't belong to the non-deterministic one. Therefore the Dyck language D′ 1* is not an EDTOL language.
We prove that every unambiguous context-free language can be recognized in O(log n) time on a parallel random access machine (P-RAM). This strengthens the result of Reif [2], who has proved that every deterministic context-free language can be recognized in O(log n) time on a P-RAM.
In a recent paper (8), Christol and al. introduce the following generalized Thue-Morse sequences over two letters a and b. Given a finite word u over {0,1}, the infinite word u has its i-th letter equal to a or b according to the number of occurrences of u in the binary expansion of i be even or odd. Černý (7) has shown that these words do not contain any factor of the form (xy)nx, with n=2...
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.