Theory of Computing Systems
Công bố khoa học tiêu biểu
* Dữ liệu chỉ mang tính chất tham khảo
Sắp xếp:
A Burnside Approach to the Finite Substitution Problem
Theory of Computing Systems - Tập 39 - Trang 15-50 - 2005
We introduce a new model of weighted automata: the desert automata. We show
that their limitedness problem is PSPACE-complete by solving the underlying
Burnside problem. As an application of this result, we give a positive
solution to the so-called finite substitution problem which was open for more
than 10 years: given recognizable languages K and L, decide whether there
exists a finite substit...... hiện toàn bộ
On the Partial Vertex Cover Problem in Bipartite Graphs - a Parameterized Perspective
Theory of Computing Systems - - Trang 1-22 - 2023
In this paper, we examine variants of the partial vertex cover problem from the perspective of parameterized algorithms. Recall that in the classical vertex cover problem (VC), we are given a graph
$$\mathbf{G = \langle V, E \rangle }$$
and a number k and asked if we can cover all of the edges in
...... hiện toàn bộ
On the Average Case of MergeInsertion
Theory of Computing Systems - Tập 64 - Trang 1197-1224 - 2020
MergeInsertion, also known as the Ford-Johnson algorithm, is a sorting algorithm which, up to today, for many input sizes achieves the best known upper bound on the number of comparisons. Indeed, it gets extremely close to the information-theoretic lower bound. While the worst-case behavior is well understood, only little is known about the average case. This work takes a closer look at the averag...... hiện toàn bộ
On the Autoreducibility of Functions
Theory of Computing Systems - Tập 46 - Trang 222-245 - 2008
This paper studies the notions of self-reducibility and autoreducibility. Our main result regarding length-decreasing self-reducibility is that any complexity class
$\mathcal{C}$
that has a (logspace) complete language and is closed under polynomial-time (logspace) padding has the property that if all ...... hiện toàn bộ
The range of a vector measure with values in a montel space
Theory of Computing Systems - Tập 5 Số 2 - Trang 145-147 - 1971
Size, index, and context-sensitivity of controlled partition grammars
Theory of Computing Systems - Tập 11 - Trang 47-60 - 1977
Controlled partition grammars (CPGs) were designed to apply to certain needs of linguists. General CPGs generate exactly all context-sensitive languages. CPGs have two parameters:size andindex. The partition index of CPGs can be bounded by two, while CPGs with partition index one generate exactly the class of context-free languages. The size (of the partition blocks) of CPGs can be bounded by two,...... hiện toàn bộ
Chinese Remaindering with Multiplicative Noise
Theory of Computing Systems - Tập 40 - Trang 33-41 - 2005
We use lattice reduction to obtain a polynomial-time algorithm for recovering an integer (up to a multiple) given multiples of its residues modulo sufficiently many primes, when the multipliers are unknown but small.
Spectral Sparsification in the Semi-streaming Setting
Theory of Computing Systems - Tập 53 - Trang 243-262 - 2012
Let G be a graph with n vertices and m edges. A sparsifier of G is a sparse graph on the same vertex set approximating G in some natural way. It allows us to say useful things about G while considering much fewer than m edges. The strongest commonly-used notion of sparsification is spectral sparsification; H is a spectral sparsifier of G if the quadratic forms induced by the Laplacians of G and H ...... hiện toàn bộ
Semiflows associated with compact and uniform processes
Theory of Computing Systems - Tập 8 - Trang 142-149 - 1974
Tổng số: 1,577
- 1
- 2
- 3
- 4
- 5
- 6
- 10