A multiparameter analysis of domino tiling with an application to concurrent systems
Resource
Theoretical Computer Science 98 (2): 263-287
Journal
Theoretical Computer Science
Journal Volume
98
Journal Issue
2
Pages
263-287
Date Issued
1992
Date
1992
Author(s)
Abstract
The complexities of two domino problems, namely the (n,k) domain problem and the (n,k) 2-person domino game problem, will be investigated with respect to parameters n and k simultaneously. The former concerns itself with tiling a rectangle of width k in the Cartesian plane using a given set of n domino types. The latter involves two players taking turns to tile a rectangle of width k using a given set of n domino types in an antagonistic fashion. (We are interested in determining whether there is a winning strategy for the first player.) It turns out that the (n,k) domino problem has upper and lower bounds of O(k*logn) andΩ(( (k - 6) 2)*logn) nondeterministic space, respectively. For the (n,k) 2-person domino game problem, we are able to show upper and lower bounds of O(nc*k) andΩ(n(k-5) 16-ε) deterministic time, respectively, for some constant c, any ε>0 and k > 17. Using the result concerning the 2-person domino game problem, we then establish a lower bound of Ω(n(k-7) 16-ε) deterministic time, any ε>0 and k>21, for the lockout problem for systems of k communicating processes in which the size of each process is bounded by n. This, together with an O(nd*k) deterministic time upper bound (which will also be shown in this paper), fully explains the role played by each of the two parameters (n and k) in the overall complexity of the problem. (It indicates that the upper bound is optimal with respect to parameters n and k.). © 1992.
Other Subjects
Mathematical Techniques - Boundary Element Method; Mathematical Techniques - Graph Theory; Probability - Game Theory; Domino Problem; Computer Metatheory
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
06.pdf
Size
1.71 MB
Format
Adobe PDF
Checksum
(MD5):5b95d9b8e515b88459d34f3f8f4b4263