Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Consistency of Multidimensiona...

Consistency of Multidimensional Combinatorial Substitutions

Timo Jolivet, Jarkko Kari, Consistency of Multidimensional Combinatorial Substitutions. In: Edward Hirsch, Juhani Karhumäki, Arto Lepistö, Michail Prilutskii (Eds.), Computer Science - Theory and Applications - 7th International Computer Science Symposium in Russia, CSR 2012, Lecture Notes in Computer Science 7353, 205–216, Springer, 2012.

Abstract:

Multidimensional combinatorial substitutions are rules that replace symbols by finite patterns of symbols in ℤ^d . We focus on the case where the patterns are not necessarily rectangular, which requires a specific description of the way they are glued together in the image by a substitution. Two problems can arise when defining a substitution in such a way: it can fail to be consistent, and the patterns in an image by the substitution might overlap.

We prove that it is undecidable whether a two-dimensional substitution is consistent or overlapping, and we provide practical algorithms to decide these properties in some particular cases.

BibTeX entry:

@INPROCEEDINGS{inpJoKa12a,
  title = {Consistency of Multidimensional Combinatorial Substitutions},
  booktitle = {Computer Science - Theory and Applications - 7th International Computer Science Symposium in Russia, CSR 2012},
  author = {Jolivet, Timo and Kari, Jarkko},
  volume = {7353},
  series = {Lecture Notes in Computer Science},
  editor = {Hirsch, Edward and Karhumäki, Juhani and Lepistö, Arto and Prilutskii, Michail},
  publisher = {Springer},
  pages = {205–216},
  year = {2012},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 1

Edit publication