The computational complexity of the unconstrained limited domino problem (with implications for logical decision problems)

Martin Fürer

doi:10.1007/3-540-13331-3_48

The computational complexity of the unconstrained limited domino problem (with implications for logical decision problems)

Martin Fürer

Eberly College of Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

25 Scopus citations

Abstract

The unconstrained domino or tiling problem is the following. Given a finite set T (of tiles), sets H,V ⊑ T×T and a cardinal k ≤ ω, does there exist a function:k×k->T such that (t(i,j),t(i+1,j))εH and (t(i,j),t(i,j+1))εV for all i,j<k ? The unlimited domino problem (k infinite) has played an important role in the process of finding the undecidability proof for the ∀ε∀ prefix class of predicate calculus. The limited domino problem is similarly connected to some decidable prefix classes. The limited domino problem is NP-complete, if k is given in unary. The same was conjectured for k given in binary, but we show an Θ (cⁿ) nondeterministic time lower bound (upper bound O(dⁿ)). As a consequence, the non-deterministic time complexity of the decision problem for the Вε ВВ class of predicate calculus lies between Θ (c^{n/log n}) and O(d^{n/log n}).

Original language	English (US)
Title of host publication	Logic and Machines
Subtitle of host publication	Decision Problems and Complexity - Proceedings of the Symposium Rekursive Kombinatorik
Editors	E. Borger, G. Hasenjaeger, D. Rodding
Publisher	Springer Verlag
Pages	312-319
Number of pages	8
ISBN (Print)	9783540133315
DOIs	https://doi.org/10.1007/3-540-13331-3_48
State	Published - 1984
Event	Symposium on Rekursive Kombinatorik, 1983 - Munster, Germany Duration: May 23 1983 → May 28 1983

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	171 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	Symposium on Rekursive Kombinatorik, 1983
Country/Territory	Germany
City	Munster
Period	5/23/83 → 5/28/83

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-13331-3_48

Cite this

Fürer, M. (1984). The computational complexity of the unconstrained limited domino problem (with implications for logical decision problems). In E. Borger, G. Hasenjaeger, & D. Rodding (Eds.), Logic and Machines: Decision Problems and Complexity - Proceedings of the Symposium Rekursive Kombinatorik (pp. 312-319). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 171 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-13331-3_48

Fürer, Martin. / The computational complexity of the unconstrained limited domino problem (with implications for logical decision problems). Logic and Machines: Decision Problems and Complexity - Proceedings of the Symposium Rekursive Kombinatorik. editor / E. Borger ; G. Hasenjaeger ; D. Rodding. Springer Verlag, 1984. pp. 312-319 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{06fb1520d3584729b8ef94a5fcdd0d72,

title = "The computational complexity of the unconstrained limited domino problem (with implications for logical decision problems)",

abstract = "The unconstrained domino or tiling problem is the following. Given a finite set T (of tiles), sets H,V ⊑ T×T and a cardinal k ≤ ω, does there exist a function:k×k->T such that (t(i,j),t(i+1,j))εH and (t(i,j),t(i,j+1))εV for all i,jn) nondeterministic time lower bound (upper bound O(dn)). As a consequence, the non-deterministic time complexity of the decision problem for the Вε ВВ class of predicate calculus lies between Θ (cn/log n) and O(dn/log n).",

author = "Martin F{\"u}rer",

note = "Publisher Copyright: {\textcopyright} 1984, Springer-Verlag.; Symposium on Rekursive Kombinatorik, 1983 ; Conference date: 23-05-1983 Through 28-05-1983",

year = "1984",

doi = "10.1007/3-540-13331-3_48",

language = "English (US)",

isbn = "9783540133315",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "312--319",

editor = "E. Borger and G. Hasenjaeger and D. Rodding",

booktitle = "Logic and Machines",

address = "Germany",

}

Fürer, M 1984, The computational complexity of the unconstrained limited domino problem (with implications for logical decision problems). in E Borger, G Hasenjaeger & D Rodding (eds), Logic and Machines: Decision Problems and Complexity - Proceedings of the Symposium Rekursive Kombinatorik. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 171 LNCS, Springer Verlag, pp. 312-319, Symposium on Rekursive Kombinatorik, 1983, Munster, Germany, 5/23/83. https://doi.org/10.1007/3-540-13331-3_48

The computational complexity of the unconstrained limited domino problem (with implications for logical decision problems). / Fürer, Martin.
Logic and Machines: Decision Problems and Complexity - Proceedings of the Symposium Rekursive Kombinatorik. ed. / E. Borger; G. Hasenjaeger; D. Rodding. Springer Verlag, 1984. p. 312-319 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 171 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - The computational complexity of the unconstrained limited domino problem (with implications for logical decision problems)

AU - Fürer, Martin

PY - 1984

Y1 - 1984

N2 - The unconstrained domino or tiling problem is the following. Given a finite set T (of tiles), sets H,V ⊑ T×T and a cardinal k ≤ ω, does there exist a function:k×k->T such that (t(i,j),t(i+1,j))εH and (t(i,j),t(i,j+1))εV for all i,jn) nondeterministic time lower bound (upper bound O(dn)). As a consequence, the non-deterministic time complexity of the decision problem for the Вε ВВ class of predicate calculus lies between Θ (cn/log n) and O(dn/log n).

AB - The unconstrained domino or tiling problem is the following. Given a finite set T (of tiles), sets H,V ⊑ T×T and a cardinal k ≤ ω, does there exist a function:k×k->T such that (t(i,j),t(i+1,j))εH and (t(i,j),t(i,j+1))εV for all i,jn) nondeterministic time lower bound (upper bound O(dn)). As a consequence, the non-deterministic time complexity of the decision problem for the Вε ВВ class of predicate calculus lies between Θ (cn/log n) and O(dn/log n).

UR - http://www.scopus.com/inward/record.url?scp=85034848491&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85034848491&partnerID=8YFLogxK

U2 - 10.1007/3-540-13331-3_48

DO - 10.1007/3-540-13331-3_48

M3 - Conference contribution

AN - SCOPUS:85034848491

SN - 9783540133315

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 312

EP - 319

BT - Logic and Machines

A2 - Borger, E.

A2 - Hasenjaeger, G.

A2 - Rodding, D.

PB - Springer Verlag

T2 - Symposium on Rekursive Kombinatorik, 1983

Y2 - 23 May 1983 through 28 May 1983

ER -

Fürer M. The computational complexity of the unconstrained limited domino problem (with implications for logical decision problems). In Borger E, Hasenjaeger G, Rodding D, editors, Logic and Machines: Decision Problems and Complexity - Proceedings of the Symposium Rekursive Kombinatorik. Springer Verlag. 1984. p. 312-319. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-13331-3_48

The computational complexity of the unconstrained limited domino problem (with implications for logical decision problems)

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this