Search

Your search keyword '"Discrete plane"' showing total 10 results
Start Over Descriptor "Discrete plane" Topic 010102 general mathematics
10 results on '"Discrete plane"'

1. Representation formula for discrete indefinite affine spheres

Author

Shimpei Kobayashi and Nozomu Matsuura

Subjects
Mathematics - Differential Geometry, Pure mathematics, Tzitzeica equation, Affine sphere, Primary 53A15, 37K10, 01 natural sciences, Loop group, 0103 physical sciences, Decomposition (computer science), FOS: Mathematics, 0101 mathematics, Mathematics, Discrete plane, 010102 general mathematics, Representation (systemics), Loop (topology), Computational Theory and Mathematics, Differential Geometry (math.DG), Liouville equation, SPHERES, 010307 mathematical physics, Geometry and Topology, Affine transformation, Discrete integrable systems, Analysis, Discrete differential geometry
Abstract

We present a representation formula for discrete indefinite affine spheres via loop group factorizations. This formula is derived from the Birkhoff decomposition of loop groups associated with discrete indefinite affine spheres. In particular we show that a discrete indefinite improper affine sphere can be constructed from two discrete plane curves., 38 pages

Published
2020

2. A discrete version of plane wave solutions of the Dirac equation in the Joyce form

Author

Volodymyr Sushch

Subjects
Discrete plane, Discretization, Applied Mathematics, 010102 general mathematics, Mathematical analysis, Plane wave, FOS: Physical sciences, Mathematical Physics (math-ph), 01 natural sciences, symbols.namesake, 39A12, 39A70, 81Q05, Scheme (mathematics), Dirac equation, 0103 physical sciences, symbols, 010307 mathematical physics, Mathematics::Differential Geometry, 0101 mathematics, Mathematics::Symplectic Geometry, Mathematical Physics, Mathematics
Abstract

We construct a discrete version of the plane wave solution to a discrete Dirac-K\"{a}hler equation in the Joyce form. A geometric discretisation scheme based on both forward and backward difference operators is used. The conditions under which a discrete plane wave solution satisfies a discrete Joyce equation are discussed., Comment: 20 pages. arXiv admin note: substantial text overlap with arXiv:1802.00040

Published
2019

3. Weak colored local rules for planar tilings

Author

Thomas Fernique, Mathieu Sablik, Institut de Mathématiques de Toulouse UMR5219 (IMT), Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique de Paris-Nord (LIPN), Université Sorbonne Paris Cité (USPC)-Institut Galilée-Université Paris 13 (UP13)-Centre National de la Recherche Scientifique (CNRS), ANR-12-JS02-0011,QuasiCool,Refroidissement des quasicristaux : des pavages aléatoires aux pavages apériodiques(2012), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), and Université Paris 13 (UP13)-Institut Galilée-Université Sorbonne Paris Cité (USPC)-Centre National de la Recherche Scientifique (CNRS)

Subjects
FOS: Computer and information sciences, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], 37B50, 52C23, 03D80, 37B10, Discrete Mathematics (cs.DM), discrete plane, General Mathematics, Existential quantification, Dynamical Systems (math.DS), Characterization (mathematics), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL], Set (abstract data type), Combinatorics, Planar, local rules, 0103 physical sciences, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, 0101 mathematics, Algebraic number, Mathematics - Dynamical Systems, Finite set, Mathematics, Applied Mathematics, 010102 general mathematics, cut and project, Linear subspace, TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, Colored, ComputingMethodologies_DOCUMENTANDTEXTPROCESSING, 010307 mathematical physics, Tiling, Computer Science - Discrete Mathematics
Abstract

A linear subspace $E$ of $\mathbb{R}^n$ has colored local rules if there exists a finite set of decorated tiles whose tilings are digitizations of $E$. The local rules are weak if the digitizations can slightly wander around $E$. We prove that a linear subspace has weak colored local rules if and only if it is computable. This goes beyond the previous results, all based on algebraic subspaces. We prove an analogous characterization for sets of linear subspaces, including the set of all the linear subspaces of $\mathbb{R}^n$., 30 pages, 10 figures

Published
2016
Full Text
View/download PDF

4. Isogonal deformation of discrete plane curves and discrete Burgers hierarchy

Author

Nozomu Matsuura, Toshinobu Kuroda, and Kenji Kajiwara

Subjects
Nonlinear Sciences - Exactly Solvable and Integrable Systems, Hierarchy (mathematics), Isogonal figure, Deformation (mechanics), Discrete plane, Plane curve, Mathematical finance, 010102 general mathematics, Mathematical analysis, FOS: Physical sciences, Geometry, 01 natural sciences, Smooth curves, Nonlinear Sciences::Exactly Solvable and Integrable Systems, 0103 physical sciences, Exactly Solvable and Integrable Systems (nlin.SI), 0101 mathematics, 010306 general physics, Differential (mathematics), Mathematics
Abstract

We study deformations of plane curves in the similarity geometry. It is known that continuous deformations of smooth curves are described by the Burgers hierarchy. In this paper, we formulate the discrete deformation of discrete plane curves described by the discrete Burgers hierarchy as isogonal deformations. We also construct explicit formulas for the curve deformations by using the solution of linear diffusion differential/difference equations.

Published
2016
Full Text
View/download PDF

5. A combinatorial approach to products of Pisot substitutions

Author

Valérie Berthé, Anne Siegel, Jérémie Bourdon, Timo Jolivet, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique de Nantes Atlantique (LINA), Centre National de la Recherche Scientifique (CNRS)-Mines Nantes (Mines Nantes)-Université de Nantes (UN), Institut de Mathématiques de Toulouse UMR5219 (IMT), Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), Dynamics, Logics and Inference for biological Systems and Sequences (Dyliss), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-GESTION DES DONNÉES ET DE LA CONNAISSANCE (IRISA-D7), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Mines Nantes (Mines Nantes)-Université de Nantes (UN)-Centre National de la Recherche Scientifique (CNRS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), and Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)

Subjects
Pure mathematics, Discrete plane, Dynamical systems theory, Applied Mathematics, General Mathematics, 010102 general mathematics, ta111, [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS], 02 engineering and technology, DUAL (cognitive architecture), 01 natural sciences, Coincidence, Discrete spectrum, Fractal, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], 0202 electrical engineering, electronic engineering, information engineering, Mathematics - Combinatorics, 020201 artificial intelligence & image processing, Fraction (mathematics), 0101 mathematics, Mathematics - Dynamical Systems, Focus (optics), Mathematics, Computer Science - Discrete Mathematics
Abstract

We define a generic algorithmic framework to prove pure discrete spectrum for the substitutive symbolic dynamical systems associated with some infinite families of Pisot substitutions. We focus on the families obtained as finite products of the three-letter substitutions associated with the multidimensional continued fraction algorithms of Brun and Jacobi-Perron. Our tools consist in a reformulation of some combinatorial criteria (coincidence conditions), in terms of properties of discrete plane generation using multidimensional (dual) substitutions. We also deduce some topological and dynamical properties of the Rauzy fractals, of the underlying symbolic dynamical systems, as well as some number-theoretical properties of the associated Pisot numbers., Comment: 32 pages, v2 with many corrections and improvements

Published
2016
Full Text
View/download PDF

6. Generating discrete planes with substitutions

Author

Valérie Berthé, Anne Siegel, Jérémie Bourdon, Timo Jolivet, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique de Nantes Atlantique (LINA), Centre National de la Recherche Scientifique (CNRS)-Mines Nantes (Mines Nantes)-Université de Nantes (UN), Dynamics, Logics and Inference for biological Systems and Sequences (Dyliss), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-GESTION DES DONNÉES ET DE LA CONNAISSANCE (IRISA-D7), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA), Mines Nantes (Mines Nantes)-Université de Nantes (UN)-Centre National de la Recherche Scientifique (CNRS), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), and Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)

Subjects
Discrete mathematics, Unimodular matrix, Discrete plane, 010201 computation theory & mathematics, 010102 general mathematics, Fraction (mathematics), 0102 computer and information sciences, 0101 mathematics, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Finite set, Dual (category theory), Mathematics
Abstract

International audience; Given a finite set S of unimodular Pisot substitutions, we provide a method for characterizing the infinite sequences over S that allow to generate a full discrete plane when, starting from a finite seed, we iterate the multidimensional dual substitutions associated with S. We apply our results to study the substitutions associated with the Brun multidimensional continued fraction algorithm.

Published
2013

7. Critical connectedness of thin arithmetical discrete planes

Author

Xavier Provençal, Valérie Berthé, Damien Jamet, Timo Jolivet, Provençal, Xavier, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Applying Discrete Algorithms to Genomics and Imagery (ADAGIO), Department of Algorithms, Computation, Image and Geometry (LORIA - ALGO), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire de Mathématiques (LAMA), Centre National de la Recherche Scientifique (CNRS)-Université Savoie Mont Blanc (USMB [Université de Savoie] [Université de Chambéry]), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Université Savoie Mont Blanc (USMB [Université de Savoie] [Université de Chambéry])-Centre National de la Recherche Scientifique (CNRS), and Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Social connectedness, Geometry, 0102 computer and information sciences, Characterization (mathematics), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Mathematics - Combinatorics, Arithmetic function, Fraction (mathematics), 0101 mathematics, Mathematics, Subtractive color, Discrete plane, 010102 general mathematics, Mathematical analysis, Infimum and supremum, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], 010201 computation theory & mathematics, Combinatorics (math.CO), Critical thickness, Computer Science - Discrete Mathematics
Abstract

An arithmetical discrete plane is said to have critical connecting thickness if its thickness is equal to the infimum of the set of values that preserve its $2$-connectedness. This infimum thickness can be computed thanks to the fully subtractive algorithm. This multidimensional continued fraction algorithm consists, in its linear form, in subtracting the smallest entry to the other ones. We provide a characterization of the discrete planes with critical thickness that have zero intercept and that are $2$-connected. Our tools rely on the notion of dual substitution which is a geometric version of the usual notion of substitution acting on words. We associate with the fully subtractive algorithm a set of substitutions whose incidence matrix is provided by the matrices of the algorithm, and prove that their geometric counterparts generate arithmetic discrete planes., Comment: 18 pages, v2 includes several corrections and is a long version of the DGCI extended abstract

Published
2013

8. Local Rules for Computable Planar Tilings

Author

Mathieu Sablik, Thomas Fernique, Institut de Mathématiques de Marseille (I2M), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique de Paris-Nord (LIPN), Université Paris 13 (UP13)-Institut Galilée-Université Sorbonne Paris Cité (USPC)-Centre National de la Recherche Scientifique (CNRS), ANR-12-JS02-0011,QuasiCool,Refroidissement des quasicristaux : des pavages aléatoires aux pavages apériodiques(2012), Université Sorbonne Paris Cité (USPC)-Institut Galilée-Université Paris 13 (UP13)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Sablik, Mathieu, and Jeunes Chercheuses et Jeunes Chercheurs - Refroidissement des quasicristaux : des pavages aléatoires aux pavages apériodiques - - QuasiCool2012 - ANR-12-JS02-0011 - JC - VALID

Subjects
FOS: Computer and information sciences, Pure mathematics, Class (set theory), Discrete Mathematics (cs.DM), Formal Languages and Automata Theory (cs.FL), discrete plane, [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS], [MATH.MATH-DS] Mathematics [math]/Dynamical Systems [math.DS], Computer Science - Formal Languages and Automata Theory, Computational Complexity (cs.CC), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Domino, lcsh:QA75.5-76.95, [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL], local rules, 0103 physical sciences, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Mathematics - Combinatorics, 0101 mathematics, F.1.1, F.1.2, F.1.3, Mathematics, lcsh:Mathematics, 010102 general mathematics, Quasicrystal, cut and project, lcsh:QA1-939, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Computer Science - Computational Complexity, [INFO.INFO-CL] Computer Science [cs]/Computation and Language [cs.CL], If and only if, Aperiodic graph, Irrational number, Key (cryptography), 010307 mathematical physics, Combinatorics (math.CO), lcsh:Electronic computers. Computer science, Tiling, Vector space, Computer Science - Discrete Mathematics
Abstract

Aperiodic tilings are non-periodic tilings characterized by local constraints. They play a key role in the proof of the undecidability of the domino problem (1964) and naturally model quasicrystals (discovered in 1982). A central question is to characterize, among a class of non-periodic tilings, the aperiodic ones. In this paper, we answer this question for the well-studied class of non-periodic tilings obtained by digitizing irrational vector spaces. Namely, we prove that such tilings are aperiodic if and only if the digitized vector spaces are computable., In Proceedings AUTOMATA&JAC 2012, arXiv:1208.2498

Published
2012

9. Subshifts as Models for MSO Logic

Author

Guillaume Theyssier, Emmanuel Jeandel, Theoretical adverse computations, and safety (CARTE), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL), Laboratoire d'informatique Fondamentale de Marseille - UMR 6166 (LIF), Université de la Méditerranée - Aix-Marseille 2-Université de Provence - Aix-Marseille 1-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Mathématiques (LAMA), Centre National de la Recherche Scientifique (CNRS)-Université Savoie Mont Blanc (USMB [Université de Savoie] [Université de Chambéry]), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), and Université Savoie Mont Blanc (USMB [Université de Savoie] [Université de Chambéry])-Centre National de la Recherche Scientifique (CNRS)

Subjects
Model theory, FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Discrete Mathematics (cs.DM), Symbolic dynamics, 0102 computer and information sciences, Characterization (mathematics), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Theoretical Computer Science, Combinatorics, Order (group theory), ACM: F.: Theory of Computation/F.1: COMPUTATION BY ABSTRACT DEVICES/F.1.1: Models of Computation/F.1.1.5: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines), 0101 mathematics, Mathematics, Discrete mathematics, Discrete plane, Hierarchy (mathematics), Model Theory, 010102 general mathematics, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], 16. Peace & justice, Subshift of finite type, Computer Science Applications, Logic in Computer Science (cs.LO), Tilings, Computational Theory and Mathematics, 010201 computation theory & mathematics, Symbolic Dynamics, Separation result, Computer Science - Discrete Mathematics, Information Systems
Abstract

We study the Monadic Second Order (MSO) Hierarchy over colourings of the discrete plane, and draw links between classes of formula and classes of subshifts. We give a characterization of existential MSO in terms of projections of tilings, and of universal sentences in terms of combinations of "pattern counting" subshifts. Conversely, we characterise logic fragments corresponding to various classes of subshifts (subshifts of finite type, sofic subshifts, all subshifts). Finally, we show by a separation result how the situation here is different from the case of tiling pictures studied earlier by Giammarresi et al., Comment: arXiv admin note: substantial text overlap with arXiv:0904.2457

Published
2009
Full Text
View/download PDF

10. Two-dimensional iterated morphisms and discrete planes

Author

Anne Siegel, Pierre Arnoux, Valérie Berthé, Arithmétique informatique (ARITH), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), and Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)

Subjects
General Computer Science, Iterative method, Approximations of π, Z2-action, 0102 computer and information sciences, 01 natural sciences, Theoretical Computer Science, Combinatorics, Multidimensional combinatorics on words, Morphism, Free monoid, Mathematics::Category Theory, 0101 mathematics, Algebraic number, ComputingMilieux_MISCELLANEOUS, Mathematics, Discrete plane, 010102 general mathematics, Quasi-finite morphism, Iterated morphism, 16. Peace & justice, Unimodular matrix, 010201 computation theory & mathematics, Iterated function, Tiling, Computer Science(all)
Abstract

Iterated morphisms of the free monoid are very simple combinatorial objects which produce infinite sequences by replacing iteratively letters by words. The aim of this paper is to introduce a formalism for a notion of two-dimensional morphisms; we show that they can be iterated by using local rules, and that they generate two-dimensional patterns related to discrete approximations of irrational planes with algebraic parameters. We associate such a two-dimensional morphism with any usual Pisot unimodular one-dimensional iterated morphism over a three-letter alphabet.

Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results