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:  
On the Partial Vertex Cover Problem in Bipartite Graphs - a Parameterized Perspective
Theory of Computing Systems - - Trang 1-22 - 2023
Vahan Mkrtchyan, Garik Petrosyan, K. Subramani, Piotr Wojciechowski
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ộ
A local implicit function theorem and application to systems of differential equations
Theory of Computing Systems - Tập 18 - Trang 251-256 - 1985
Vaclav Dolezal, Shiva Shankar
A local implicit function theorem is proved which assumes certain injectivity rather than differentiability. Moreover, there is given a result on solvability of noncanonic systems of differential equations which arise in optimal control and network theory.
Some Bounds on the Computational Power of Piecewise Constant Derivative Systems
Theory of Computing Systems - Tập 32 - Trang 35-67 - 1999
O. Bournez
We study the computational power of Piecewise Constant Derivative (PCD) systems. PCD systems are dynamical systems defined by a piecewise constant differential equation and can be considered as computational machines working on a continuous space with a continuous time. We show that the computation time of these machines can be measured either as a discrete value, called discrete time, or as a co...... hiện toàn bộ
The (Non)Enumerability of the Determinant and the Rank
Theory of Computing Systems - Tập 36 - Trang 359-374 - 2003
Alina Beygelzimer, Mitsunori Ogihara
We investigate the complexity of enumerative approximation of two fundamental problems in linear algebra, computing the rank and the determinant of a matrix. We show that both are as hard to approximate (in the enumerative sense) as to compute exactly. In particular, if there exists an enumerator that, given a matrix over some finite field, outputs a list of constantly many numbers, one of which ...... hiện toàn bộ
Các khía cạnh phân loại và hình thái học của ngôn ngữ hình thức Dịch bởi AI
Theory of Computing Systems - Tập 13 - Trang 255-273 - 1979
Evelyn Nelson
Bài báo này đặt công trình của H. Walter về phân loại ngữ pháp và ngôn ngữ thông qua hình thái học vào một khung tổng quát hơn và cung cấp các chứng minh ngắn gọn cho các kết quả chính của ông. Ngoài ra, bài báo cũng chứng minh rằng mọi ngữ pháp đều tương đương về mặt hình thái học với một ngữ pháp ở dạng chuẩn, rằng hình thái rời rạc có thể được hiện thực hóa trên mọi ngôn ngữ không ngữ cảnh, và ...... hiện toàn bộ
#ngữ pháp #ngôn ngữ không ngữ cảnh #hình thái học #phân loại ngôn ngữ #thuật toán #tính hữu hạn
Puzzles, Art, and Magic with Algorithms
Theory of Computing Systems - Tập 39 Số 3 - Trang 473-481 - 2006
Erik D. Demaine, Martin L. Demaine
Relationships between pushdown automata with counters and complexity classes
Theory of Computing Systems - Tập 9 - Trang 248-264 - 1975
Burkhard Monien
In this paper a machine model is defined whose access to the storage cells is controlled by means of address registers. It is shown that every set acceptable by such a machine within time boundc⋅n p,p ∈ ℕ, is accepted by a deterministic 2p-head two-way pushdown automaton which has additional counters of length log2 n. On the other hand every set acceptable by a deterministicp-head two-way pushdown...... hiện toàn bộ
Series Parallel Digraphs with Loops
Theory of Computing Systems - Tập 53 - Trang 126-158 - 2012
Stefan Gulan
In the conversion of finite automata to regular expressions, an exponential blowup in size can generally not be avoided. This is due to graph-structural properties of automata which cannot be directly encoded by regular expressions and cause the blowup combinatorially. In order to identify these structures, we generalize the class of arc-series-parallel digraphs beyond the acyclic case. The result...... hiện toàn bộ
Omega-Rational Expressions with Bounded Synchronization Delay
Theory of Computing Systems - - 2015
Volker Diekert, Manfred Kufleitner
On Short Paths Interdiction Problems: Total and Node-Wise Limited Interdiction
Theory of Computing Systems - Tập 43 - Trang 204-233 - 2007
Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled Elbassioni, Vladimir Gurvich, Gabor Rudolf, Jihui Zhao
Given a directed graph G=(V,A) with a non-negative weight (length) function on its arcs w:A→ℝ+ and two terminals s,t∈V, our goal is to destroy all short directed paths from s to t in G by eliminating some arcs of A. This is known as the short paths interdiction problem. We consider several versions of it, and in each case analyze two subcases: total limited interdiction, when a fixed number k of ...... hiện toàn bộ
Tổng số: 1,577   
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 10