Found 44 Documents (Results 1–44)
The domino problem is undecidable on every rhombus subshift. (English) Zbl 07766937
Drewes, Frank (ed.) et al., Developments in language theory. 27th international conference, DLT 2023, Umeå, Sweden, June 12–16, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13911, 100-112 (2023).
MSC:
68Q45
Parametrization by horizontal constraints in the study of algorithmic properties of \(\mathbb{Z}^2\)-subshifts of finite type. (English) Zbl 1519.37013
The aperiodic domino problem in higher dimension. (English) Zbl 07836586
Berenbrink, Petra (ed.) et al., 39th international symposium on theoretical aspects of computer science, STACS 2022, Marseille, France, virtual conference, March 15–18, 2022. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 219, Article 19, 15 p. (2022).
MSC:
68Qxx
The undecidability of conditional affine information inequalities and conditional independence implication with a binary constraint. (English) Zbl 1534.94040
MSC:
94A17
Domino problem under horizontal constraints. (English) Zbl 07650911
Paul, Christophe (ed.) et al., 37th international symposium on theoretical aspects of computer science, STACS 2020, Montpellier, France, March 10–13, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 154, Article 26, 15 p. (2020).
MSC:
68Qxx
Decidability and periodicity of low complexity tilings. (English) Zbl 07650899
Paul, Christophe (ed.) et al., 37th international symposium on theoretical aspects of computer science, STACS 2020, Montpellier, France, March 10–13, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 154, Article 14, 12 p. (2020).
MSC:
68Qxx
The undecidability of the domino problem. (English) Zbl 1457.52017
Akiyama, Shigeki (ed.) et al., Substitution and tiling dynamics: introduction to self-inducing structures. Lecture notes from the research school on tiling dynamical systems, CIRM Jean-Morlet Chair, Marseille, France, Fall 2017. Cham: Springer. Lect. Notes Math. 2273, 293-357 (2020).
Necessary conditions for tiling finitely generated amenable groups. (English) Zbl 1440.37027
Reviewer: Hasan Akin (Gaziantep)
The domino problem is undecidable on surface groups. (English) Zbl 1539.03136
Rossmanith, Peter (ed.) et al., 44th international symposium on mathematical foundations of computer science, MFCS 2019, Aachen, Germany, August 26–30, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 138, Article 46, 14 p. (2019).
Low-complexity tilings of the plane. (English) Zbl 1434.68264
Hospodár, Michal (ed.) et al., Descriptional complexity of formal systems. 21st IFIP WG 1.02 international conference, DCFS 2019, Košice, Slovakia, July 17–19, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11612, 35-45 (2019).
Convex domino towers. (English) Zbl 1355.05076
Efficient domination for some subclasses of \(P_6\)-free graphs in polynomial time. (English) Zbl 1417.05150
Mayr, Ernst W. (ed.), Graph-theoretic concepts in computer science. 41st international workshop, WG 2015, Garching, Germany, June 17–19, 2015. Revised papers. Berlin: Springer. Lect. Notes Comput. Sci. 9224, 78-89 (2016).
Fast domino tileability. (English) Zbl 1350.68267
Knight tiles: particles and collisions in the realm of 4-way deterministic tilings. (English) Zbl 1425.05027
Shur, Arseny M. (ed.) et al., Developments in language theory. 18th international conference, DLT 2014, Ekaterinburg, Russia, August 26–29, 2014. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 8633, 227-238 (2014).
MSC:
05B45
Arctic circles, domino tilings and square Young tableaux. (English) Zbl 1258.60014
Reviewer: Hsien-Kuei Hwang (Taipei)
The reconstruction of a bicolored domino tiling from two projections. (English) Zbl 1055.68614
Braquelaire, Achille (ed.) et al., Discrete geometry for computer imagery. 10th international conference, DGCI 2002, Bordeaux, France, April 3–5, 2002. Proceedings. Berlin: Springer (ISBN 3-540-43380-5). Lect. Notes Comput. Sci. 2301, 136-144 (2002).
Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs. (English) Zbl 0906.05067
Reviewer: H.Müller (Jena)
Simple sentences that are hard to decide. (English) Zbl 0733.03031
Reviewer: Zheng Xizhong (Nanjing)
Domino games and complexity. (English) Zbl 0711.68044
Domino threads and complexity. (English) Zbl 0631.03028
Computation theory and logic, D. Rödding Occas. 50th Anniv. Birth, Lect. Notes Comput. Sci. 270, 131-142 (1987).
Domino-tiling games. (English) Zbl 0618.68045
Reviewer: A.Kreczmar
Recurring dominoes: Making the highly undecidable highly understandable. (English) Zbl 0531.68003
Topics in the theory of computation, Sel. Pap. Int. Conf., Borgholm/Swed. 1983, Ann. Discrete Math. 24, 51-72 (1985).
Propositional dynamic logic with strong loop predicate. (English) Zbl 0552.68036
Mathematical foundations of computer science, Proc. 11th Symp., Praha/Czech. 1984, Lect. Notes Comput. Sci. 176, 573-581 (1984).
Reviewer: H.Nishimura
The computational complexity of the unconstrained limited domino problem (with implications for logical decision problems). (English) Zbl 0549.68037
Logic and machines: decision problems and complexity, Proc. Symp., Münster/Ger. 1983, Lect. Notes Comput. Sci. 171, 312-319 (1984).
Recurring dominoes: making the highly undecidable highly understandable. (English) Zbl 0531.68002
Foundations of computation theory, Proc. int. FCT-Conf., Borgholm/Swed. 1983, Lect. Notes Comput. Sci. 158, 177-194 (1983).
A measure of complexity for combinatorial decision problems of the tiling variety. (English) Zbl 0414.03008
Proc. Conf. theoretical computer science, Waterloo/Ontario 1977, 94-99 (1977).
Filter Results by …
Document Type
- Journal Articles (28)
- Collection Articles (15)
- Books (1)
all
top 5
Author
- Kari, Jarkko (6)
- Aubrun, Nathalie (3)
- Moutot, Etienne (3)
- Ebbinghaus, Heinz-Dieter (2)
- Goodman-Strauss, Chaim (2)
- Grädel, Erich (2)
- Harel, David (2)
- Hellouin De Menibus, Benjamin (2)
- Jeandel, Emmanuel (2)
- Sablik, Mathieu (2)
- Amilhastre, Jérôme (1)
- Ballier, Alexis (1)
- Barbieri, Sebastián (1)
- Bartholdi, Laurent (1)
- Brandstädt, Andreas (1)
- Brown, Tricia Muldoon (1)
- Callard, Antonin (1)
- Chlebus, Bogdan Stanislaw (1)
- Cornejo, Hugo Maturana (1)
- Danecki, Ryszard (1)
- Eschen, Elaine M. (1)
- Esnay, Julien (1)
- Esnay, Solène J. (1)
- Esperet, Louis (1)
- Friese, Erik (1)
- Frosini, Andrea (1)
- Fürer, Martin (1)
- Giocanti, Ugo (1)
- Hellouin, De Menibus Benjamin (1)
- Janssen, Philippe (1)
- Klarner, David Anthony (1)
- Le Gloannec, Bastien (1)
- Legrand-Duchesne, Clément (1)
- Lewis, Harry R. (1)
- Li, Cheuk Ting (1)
- Luby, Michael G. (1)
- Lukkarila, Ville (1)
- Lutfalla, Victor H. (1)
- Lutz, Carsten (1)
- Noûs, Camille (1)
- Ollinger, Nicolas (1)
- Pachter, Lior (1)
- Pak, Igor (1)
- Picouleau, Christophe (1)
- Pollack, Jordan B. (1)
- Randall, Dana J. (1)
- Romik, Dan (1)
- Sheffer, Adam (1)
- Simi, Giulia (1)
- Sinclair, Alistair (1)
- Stein, Maya Jakobine (1)
- Tassy, Martin (1)
- Vanier, Pascal (1)
- Vilarem, Marie-Catherine (1)
- Worman, Chris (1)
- Yang, Boting (1)
all
top 5
Serial
- Theor. Comput. Sci. (6)
- Discrete Math. (2)
- J. Comput. Syst. Sci. (2)
- SIAM J. Comput. (2)
- Discrete Contin. Dyn. Syst. (2)
- Groups Geom. Dyn. (2)
- Discrete Appl. Math. (1)
- IEEE Trans. Inf. Theory (1)
- Ann. Probab. (1)
- J. Comb. Theory, Ser. B (1)
- Z. Math. Logik Grundlagen Math. (1)
- Discrete Comput. Geom. (1)
- Inf. Comput. (1)
- Theory Comput. Syst. (1)
- Discrete Math. Theor. Comput. Sci. (1)
- J. Integer Seq. (1)
- Fundam. Inform. (1)
- ACM Trans. Comput. Log. (1)
Software
- OEIS (2)
- Mathematica (1)
