Yen, Hsu-ChunHsu-ChunYen2009-03-042018-07-062009-03-042018-07-061992https://www.scopus.com/inward/record.uri?eid=2-s2.0-0026869547&doi=10.1016%2f0304-3975%2892%2990004-Y&partnerID=40&md5=79fd917d33e1b02d584ee69f06697a0eThe 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.application/pdf1790695 bytesapplication/pdfen-USMathematical Techniques - Boundary Element Method; Mathematical Techniques - Graph Theory; Probability - Game Theory; Domino Problem; Computer Metatheoryjournal article10.1016/0304-3975(92)90004-Y2-s2.0-0026869547http://ntur.lib.ntu.edu.tw/bitstream/246246/142308/1/06.pdf