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:
Puzzles, Art, and Magic with Algorithms
Theory of Computing Systems - Tập 39 Số 3 - Trang 473-481 - 2006
Relationships between pushdown automata with counters and complexity classes
Theory of Computing Systems - Tập 9 - Trang 248-264 - 1975
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......
Series Parallel Digraphs with Loops
Theory of Computing Systems - Tập 53 - Trang 126-158 - 2012
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......
Polynomial-Space Decidable Membership Problems for Recurrent Systems over Sets of Natural Numbers
Theory of Computing Systems - Tập 41 - Trang 257-289 - 2007
A finite recurrent system over sets of natural numbers of dimension n is a pair composed of n n-ary functions over sets of natural numbers and an n-tuple of singleton sets of natural numbers. Every function is applied to the entries of the tuple and computes a set of natural numbers, that may also be empty. The results are composed into another tuple, and the process is started anew. Thus, a finit......
Axiomatizing Kolmogorov Complexity
Theory of Computing Systems - Tập 52 - Trang 148-161 - 2012
We revisit the axiomatization of Kolmogorov complexity given by Alexander Shen, currently available only in Russian language. We derive an axiomatization for conditional plain Kolmogorov complexity. Next we show that the axiomatic system given by Shen cannot be weakened (at least in any natural way). In addition we prove that the analogue of Shen’s axiomatic system fails to characterize prefix-fre......
Efficient Detection of Determinacy Races in Cilk Programs
Theory of Computing Systems - Tập 32 - Trang 301-326 - 1999
A parallel multithreaded program that is ostensibly deterministic may nevertheless behave nondeterministically due to bugs in the code. These bugs are called determinacy races, and they result when one thread updates a location in shared memory while another thread is concurrently accessing the location. We have implemented a provably efficient determinacy-race detector for Cilk, an algorithmic m......
A partial equivalence between shared-memory and message-passing in an asynchronous fail-stop distributed environment
Theory of Computing Systems - Tập 26 - Trang 21-39 - 2005
This paper presents a schematic algorithm for distributed systems. This schematic algorithm uses a “black-box” procedure for communication, the output of which must meet two requirements: a global-order requirement and a deadlock-free requirement. This algorithm is valid in any distributed system model that can provide such a communication procedure that complies with these requirements. Two such ......
Sharing Resources at Nonuniform Access Rates
Theory of Computing Systems - Tập 34 Số 1 - Trang 13-26 - 2000
We introduce DPPr (for ``Dining Philosophers Problem with rates'') as a generalization of the heavy-load case of the Dining Philosophers Problem (DPP). In DPPr, processes are required to be scheduled to access shared resources with prespecified relative frequencies. DPPr is an abstraction of resource-sharing problems to which the synchronization of some distributed algorithms for neural-network mo......
Tổng số: 1,577
- 1
- 2
- 3
- 4
- 5
- 6
- 10