Search

Several articles deal with tilings with squares and dominoes of the well-known regular square mosaic in Euclidean plane, but not any with the hyperbolic regular square mosaics. In this article, we examine the tiling problem with colored squares and dominoes of one type of the possible hyperbolic generalization of $(2\times n)$-board., Comment: 10 pages, 8 figures

This paper defines a tiling problem related to the automorphism group of $$F_2$$ . Our main result is that the corresponding tilings admit a complete, concrete classification.

We study the computational hardness of the tiling puzzle with polyominoes, where a polyomino is a right-angled polygon (i.e., a polygon made by connecting unit squares along their edges). In the tiling problem, we are given a right-angled polygon P and a set S of polyominoes, and asked whether P can be covered without any overlap using translated copies of polyominoes in S. In this paper, we focus on trominoes and bars as polyominoes; a tromino is a polyomino consisting of three unit squares, and a bar is a rectangle of either height one or width one. Notice that there are essentially two shapes of trominoes, that is, I-shape (i.e., a bar) and L-shape. We consider the tiling problem when restricted to only L-shape trominoes, only I-shape trominoes, both L-shape and I-shape trominoes, or only two bars. In this paper, we prove that the tiling problem remains NP-complete even for such restricted sets of polyominoes. All reductions are carefully designed so that we can also prove the # P-completeness and ASP-completeness of the counting and the another-solution-problem variants, respectively. Our results answer two open questions proposed by Moore and Robson (Discrete Comput Geom 26:573–590, 2001) and Pak and Yang (J Comb Theory 120:1804–1816, 2013).

Adding propositional quantification to the modal logics $\mathsf{K, T}$ or S4 is known to lead to undecidability but CTL with propositional quantification under the tree semantics (QCTLt) admits a non-elementary Tower-complete satisfiability problem. We investigate the complexity of strict fragments of $\mathsf{QCTL}^{t}$ as well as of the modal logic $\mathsf{K}$ with propositional quantification under the tree semantics. More specifically, we show that $\mathsf{QCTL}^{t}$ restricted to the temporal operator EX is already Tower-hard, which is unexpected as EX can only enforce local properties. When QCTLt restricted to EX is interpreted on N-bounded trees for some $N\geq 2$ , we prove that the satisfiability problem is $\mathbf{AExp}_{\mathrm{pol}^{-}}$ complete; $\mathbf{AExp}_{\mathrm{pol}}$ -hardness is established by reduction from a recently introduced tiling problem, instrumental for studying the model-checking problem for interval temporal logics. As consequences of our proof method, we prove Tower-hardness of QCTLtrestricted to EF or to EXEF and of the well-known modal logics $\mathsf{K}$ , KD, GL, S4, K4 and D4, with propositional quantification under a semantics based on classes of trees.

We consider a certain tiling problem of a planar region in which there are no long horizontal or vertical strips consisting of copies of the same tile. Intuitively speaking, we would like to create a dappled pattern with two or more kinds of tiles. We give an efficient algorithm to turn any tiling into one satisfying the condition, and discuss its applications in texturing.

The Square Tiling Problem was recently introduced as equivalent to the problem of reconstructing an image from patches and a possible general-purpose indexing tool. Unfortunately, the Square Tiling Problem was shown to be NP -hard. A 1/2-approximation is known.We show that if the tile alphabet is fixed and finite, there is a Polynomial Time Approximation Scheme (PTAS) for the Square Tiling Problem with approximation ratio of ( 1 - ? 2 log ? n ) for any given ? ? 1 .Another topic handled in this paper is the NP -hardness of the Tiling problem with an infinite alphabet. We show that when the alphabet is not bounded, even the decision version for rectangles of size 3n is NP -Complete.

A lattice L L in R n \mathbb {R}^n is said to be equivalent to an integral lattice if there exists a real number r r such that the dot product of any pair of vectors in r L rL is an integer. We show that if n ≥ 3 n \geq 3 and L L is equivalent to an integral lattice, then there is no measurable Steinhaus set for L L , a set which no matter how translated and rotated contains exactly one vector in L L .

In this article we solve the tiling problem for hyperbolic and Euclidean regular polygons whose edges are notched with matching bumps and nicks.

In this paper, we consider several variations of the following basic tiling problem: given a sequence of real numbers with two size-bound parameters, we want to find a set of tiles of maximum total weight such that each tiles satisfies the size bounds. A solution to this problem is important to a number of computational biology applications such as selecting genomic DNA fragments for PCR-based amplicon microarrays and performing homology searches with long sequence queries. Our goal is to design efficient algorithms with linear or near-linear time and space in the normal range of parameter values for these problems. For this purpose, we first discuss the solution to a basic online interval maximum problem via a sliding-window approach and show how to use this solution in a nontrivial manner for many of the tiling problems introduced. We also discuss NP-hardness results and approximation algorithms for generalizing our basic tiling problem to higher dimensions. Finally, computational results from applying our tiling algorithms to genomic sequences of five model eukaryotes are reported.

� AND R. DANIELMAULDIN † Abstract. WesurveysomeresultsandproblemsarisingfromaclassicproblemofSteinhaus: IsthereasubsetSof R 2 suchthateachisometriccopyof Z 2 (thelatticepointsintheplane) meetsSinexactlyonepoint. §1. Introduction. We survey in this paper some of the known results, methods, and open questions concerningSteinhaus sets. Although this is primarilyasurveyarticle,weincludeafewnewresultssuchastheexistence of Steinhaus sets for certain other rectangular lattices, e.g., theorem 2.11. ThenotionofaSteinhaussetcanbeintroducedatvariouslevelsofgenerality. SteinhausaskedinthelatefiftiesiftherecouldbeasetS ⊆ R 2 suchthatS meetseveryisometriccopyoftheintegerlattice Z × Zinexactlyonepoint. WeareaskingthisquestioninthecontextofZFC,thatis,assumingchoice, but the question remains interesting in the context of ZF as well. Also, the question can be immediately extended to higher dimensionsand other lattices. Thus, ifL ⊆ R m is a lattice andn ≥m, we can ask if there is a setS ⊆ R n whichmeetseveryð(L)isexactlyonepoint,whereð: R n → R n is an isometry (and we view R m ⊆ R n in the usual way). This will be the contextformostofthediscussionofthispaper,andwewillinfactgenerally havem=n. Inthiscase,werefertosuchasetS,ifitexists,asaSteinhaus setforthelatticeL. LetuscommentthatSteinhaus'questionconcernsthe existence of a "simultaneous tiling" of the plane. To say a setE tiles the plane means the translates ofE by the lattice points in Z 2 partitions the plane. So,SisaSteinhaussetifandonlyifeachrotatedcopyofStiles R 2 . Wecangeneralizethebasicnotionsconsiderably. Given(X, A,f),where X is a set, A ⊆ P(X) is a family of subsets ofX, andf: A →CARD is

The MAX–MIN tiling problem is as follows. We are given A [1,…,n][1,…,n] , a two-dimensional array where each entry A [i][j] stores a non-negative number. Define a tile of A to be a subarray A [l,…,r][t,…,b] of A , the weight of a tile to be the sum of all array entries in it, and a tiling of A to be a collection of tiles of A such that each entry A [i][j] is contained in exactly one tile. Given a weight bound W the goal of our MAX–MIN tiling problem is to find a tiling of A such that: (1) each tile is of weight at least W (the MIN condition), and (2) the number of tiles is maximized (the MAX condition). The MAX–MIN tiling problem is known to be NP-hard; here, we present first non-trivial approximations algorithms for solving it.

Recently, using Fourier transform methods, it was shown that there is no measurable Steinhaus set in R 3 , a set which no matter how translated and rotated contains exactly one integer lattice point. Here, we show that this argument cannot generalize to any lattice and, on the other hand, give some lattices to which this method applies. We also show there is no measurable Steinhaus set for a special honeycomb lattice, the standard tetrahedral lattice in R 3 .

International audience; Particles and collisions are convenient construction tools to compute inside tilings and enforce complex sets of tilings with simple tilesets. Locally enforceable particles being incompatible with expansivity in the orthogonal direction, a compromise has to be found to combine both notions in a same tileset. This paper introduces knight tiles: a framework to construct 4-way deterministic tilings, that is tilings completely determined by any infinite diagonal of tiles, for which local particles and collisions with many slopes can still be constructed while being expansive in infinitely many directions. The framework is then illustrated by an elegant yet simple construction to mark a diagonal with a 4-way deterministic knight tileset.

We study the following tiling problem in d dimensions: given a d-dimensional rectangular array of nonnegative numbers and an integer p, partition the array into at most p rectangular subarrays so that the maximum weight of any subarray is minimized; the weight of a subarray is the sum of its elements. The rectangular tiling problem is motivated by applications in data mining, data partitioning, and video compression. Recently, Khanna, Muthukrishnan, and Paterson SODA '98], showed that the tiling problem is NP-complete and gave a 2.5-approximation algorithm for d=2.In this paper, we extend their result to multidimensional arrays and give an algorithm with approximation ratio d+32, for d?2. The algorithm can be implemented to run in worst-case time O(N+plogN) time, where N is the size of the array, and the constant is of the order d!. We also obtain a similar algorithm for the dual tiling problem, where the goal is to compute a tiling of weight at most W using as few tiles as possible. Our algorithm yields an approximation factor (2d+1).We implemented our algorithm and ran simulation tests on multidimensional arrays with random data. In our limited experiments, the algorithm always produced approximations that were no worse than factor two from the optimal.

have the same numerator. These fractions simplify to 1 a3993 and 103993 respectively. _T3_102 355 In this paper, we provide a combinatorial interpretation for the numerators and denominators of continued fractions which makes this reversal phenomenon easy to see. Through the use of counting arguments, we illustrate how this and other important identities involving continued fractions can be easily visualized, derived, and remembered. We begin by defining some basic terminology. Given an infinite sequence of integers ao ? 0, a, ? 1, a2 ? 1,. let [ao, a n.a,] denote the finite continued fraction

The tiling problem is a typical NP-complete problem, where the polyominoes are to be arranged without a gap on a finite checkerboard. In this study, the arrangement of l polyominoes on an m ×n checkerboard is considered. As the first step, the conventional parallel algorithm using the maximum neural network is verified. Then, the authors propose a solution procedure for the tiling problem, where the analog neural network is used in addition to the fitting function. Lastly, the proposed method and the conventional method are compared, and it is shown that the proposed method is also effective for more complex tiling problems. © 1999 Scripta Technica, Electron Comm Jpn Pt 3, 83(2): 1–10, 2000

Several results are proved related to a question of Steinhaus: is there a set E ⊂ℝ 2 such that the image of E under each rigid motion of IR2 contains exactly one lattice point? Assuming measurability, the analogous question in higher dimensions is answered in the negative, and on the known partial results in the two dimensional case are improved on. Also considered is a related problem involving finite sets of rotations.

Deciding if a given set of Wang tiles admits a tiling of the plane is decidable if the number of Wang tiles (or the number of colors) is bounded, for a trivial reason, as there are only finitely many such tilesets. We prove however that the tiling problem remains undecidable if the difference between the number of tiles and the number of colors is bounded by 43. One of the main new tool is the concept of Wang bars, which are equivalently inflated Wang tiles or thin polyominoes., Comment: In Proceedings AUTOMATA&JAC 2012, arXiv:1208.2498

We study the expressibility problem: given a finite constraint language Γ on a finite domain and another relation R, can Γ express R? We prove, by an explicit family of examples, that the standard witnesses to expressibility and inexpressibility (gadgets/formulas/conjunctive queries and polymorphisms respectively) may be required to be exponentially larger than the instances. We also show that the full expressibility problem is co-NEXPTIME-hard. Our proofs hinge on a novel interpretation of a tiling problem into the expressibility problem.

In this paper, we investigate tilings of tori and rectangles with rectangular tiles. We present necessary and sufficient conditions for the existence of an integer C such that any torus, having dimensions greater than C, is tiled with two given rectangles (C depending on the dimensions of the tiles). We also give sufficient conditions to tile a sufficiently large n-dimensional rectangle with a set of (n-dimensional) rectangular tiles. We do this by combining the periodicity of some particular tilings and results concerning the so-called Frobenius number.

In this paper, we consider the periodic tiling problem which was proved undecidable in the Euclidean plane by Yu. Gurevich and I. Koriakov, see [3]. Here, we prove that the same problem for the hyperbolic plane is also undecidable.

Interval temporal logics are based on temporal structures where time intervals, rather than time instants, are the primitive ontological entities. They employ modal operators corresponding to various relations between intervals, known as Allen’s relations. Technically, validity in interval temporal logics translates to dyadic second-order logic, thus explaining their complex computational behavior. The full modal logic of Allen’s relations, called HS, has been proved to be undecidable by Halpern and Shoham under very weak assumptions on the class of interval structures, and this result was discouraging attempts for practical applications and further research in the field. A renewed interest has been recently stimulated by the discovery of interesting decidable fragments of HS. This paper contributes to the characterization of the boundary between decidability and undecidability of HS fragments. It summarizes known positive and negative results, it describes the main techniques applied so far in both directions, and it establishes a number of new undecidability results for relatively small fragments of HS.

In this paper, we consider the finite tiling problem which was proved undecidable in the Euclidean plane by Jarkko Kari, see [5]. Here, we prove that the same problem for the hyperbolic plane is also undecidable.

We consider the following tiling problem: Given a d dimensional array A of size n in each dimension, containing non-negative numbers and a positive integer p, partition the array A into at most p disjoint rectangular subarrays called rectangles so as to minimise the maximum weight of any rectangle. The weight of a subarray is the sum of its elements. In the paper we give a $\frac{d+2}{2}$-approximation algorithm that is tight with regard to the only known and used lower bound so far.

Simultaneous tiling for several different translational sets has been studied rather extensively, particularly in connection with the Steinhaus problem. The study of orthonormal wavelets in recent years, particularly for arbitrary dilation matrices, has led to the study of multiplicative tilings by the powers of a matrix. In this paper we consider the following simultaneous tiling problem: Given a lattice in $\L\in \R^d$ and a matrix $A\in\GLd$, does there exist a measurable set $T$ such that both $\{T+\alpha: \alpha\in\L\}$ and $\{A^nT: n\in\Z\}$ are tilings of $\R^d$? This problem comes directly from the study of wavelets and wavelet sets. Such a $T$ is known to exist if $A$ is expanding. When $A$ is not expanding the problem becomes much more subtle. Speegle \cite{Spe03} exhibited examples in which such a $T$ exists for some $\L$ and nonexpanding $A$ in $\R^2$. In this paper we give a complete solution to this problem in $\R^2$., Comment: 16 pages, no figures

In this survey I will try to describe how Fourier analysis is used in the study of translational tiling. Right away I will emphasize two restrictions that separate this area from the general theory of tilings.

The tiling problem is closely connected with a number of problems of information theory. We show that the Wang-Moore conjecture is valid for the one dimensional case. Namely, any set of templates which permits a tiling of the set ℤ of integers also permits a periodic tiling. We also show that any tiling of ℤ by one template is necessarily periodic. The obtained results are also valid for tiling of the set IR of real numbers.

Aperturbation of a tiling of a region inR n is a set of isometries, one applied to each tile, so that the images of the tiles tile the same region. We show that a locally finite tiling of an open region inR 2 with tiles which are closures of their interiors isrigid in the following sense: any sufficiently small perturbation of the tiling must have only “earthquake”-type discontinuities, that is, the discontinuity set consists of straight lines and arcs of circles, and the perturbation near such a curve shifts points along the direction of that curve. We give an example to show that this type of rigidity does not hold inR n , forn>2. Using rigidity in the plane we show that any tiling problem with a finite number of tile shapes (which are topological disks) is equivalent to a polygonal tiling problem, i.e. there is a set of polygonal shapes with equivalent tiling combinatorics.

A tiling of the plane with polygonal tiles is said to be strict if any point common to two tiles is a vertex of both or a vertex of neither. A triangle is said to be rational if its sides have rational length. Recently R.B. Eggleton asked if it is possible to strictly tile the plane with rational triangles using precisely one triangle from each congruence class. In this paper we constructively prove the existence of such a tiling by a suitable modification of the technique suggested by Eggleton. The theory of rational points on elliptic curves, in particular, the Nagell-Lutz theorem, plays a crucial role in completing the proof.

In cluster approximations for lattice systems the thermodynamic behavior of the infinite system is inferred from that of a relatively small, finite subsystem (cluster), approximations being made for the influence of the surrounding system. In this context we study, for translation-invariant classical lattice systems, the conditions under which a state for a cluster admits an extension to a global translation-invariant state. This extension problem is related to undecidable tiling problems. The implication is that restrictions of global translation-invariant states cannot be characterized purely locally in general. This means that there is an unavoidable element of uncertainty in the application of a cluster approximation.

The classic Banach Contraction Principle states that any contraction on a complete metric space has a unique fixed point. Rather than requiring that a single operator be a contraction, we consider a minimum involving a set of powers of that operator and derive fixed-point results. Ordinary analytical techniques would be extremely unwieldy, and so we develop a method for attacking this problem by considering a related problem on tiling the integers.

We give a new construction of strongly aperiodic set of tiles in H2, exhibiting a kind of hierarchical structure, simplifying the central framework of Margenstern’s proof that the Domino Problem is undecidable in the hyperbolic plane (Margenstern (2008) [16]).

Many applications have a need for indexing unstructured data. It turns out that a similar ad-hoc method is being used in many of them – that of considering small particles of the data.In this paper we formalize this concept as a tiling problem and consider the efficiency of dealing with this model in the pattern matching setting.We present an efficient algorithm for the one-dimensional tiling problem, and the one-dimensional tiled pattern matching problem. We prove the two-dimensional problem is hard and then develop an approximation algorithm with an approximation ratio converging to 2. We show that other two-dimensional versions of the problem are also hard, regardless of the number of neighbors a tile has.

Two structurally defined types of NP sets are studied. k-simple sets are defined and shown to exist in NP. Other properties of these sets are investigated. k-creative sets, as previously defined by Joseph and Young [10], are next considered. A new condition is given which implies that a set is k-creative. Several previously considered NP-complete sets are proved to be k-creative.

This paper describes a neuro-based optimization algorithm for tiling with polyominoes. First, we review the previous neuro-based parallel algorithm for the tiling problem where l/spl times/m/spl times/n maximum neural array is required for an m/spl times/n checkerboard. Next, we propose a robust neuro-based tiling algorithm using the modified energy function which includes the fitting violation function of the polyominoes and the analog neural array. Finally, we compare our algorithm with the previous one and show that our method is much more vigorous and practical for larger tiling problems.

Many interesting combinatorial problems were found to be NP-complete. Since there is little hope to solve them fast in the worst case, researchers look for algorithms which are fast just “on average,” This matter is sensitive to the choice of a particular NP-complete problem and a probability distribution of its instances. Some of these tasks are easy and some not. But one needs a way to distinguish the “difficult on average” problems. Such negative results could not only save “positive” efforts but may also be used in areas (like cryptography) where hardness of some problems is a frequent assumption. It is shown in [1] that the Tiling problem with uniform distribution of instances has no polynominal “on average” algorithm, unless every NP-problem with every simple probability distribution has it.