• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

A Note on Defect Theorems for 2-Dimensional Words and Trees

Mari Huova, A Note on Defect Theorems for 2-Dimensional Words and Trees. Journal of Automata, Languages and Combinatorics 14(3-4/2009), 203–209, 2010.

Abstract:

Defect theorem, a classical result of combinatorics on words, can be extended on 2-dimensional words and trees under some restrictions. In this note we answer to two open problems stated in W. Moczurad, (Theor. Inform. Appl. 41, 2007): whether the defect property holds or does not hold for three rectangles and for two figures of unrestricted shape. We give two counterexamples to show that the defect property fails in both situations. This completes the analysis of the defect property with 2-dimensional words in the classes of dominoes, squares, rectangles and figures with unrestricted shape. In addition, we examine the same question of the validity of the defect property with trees.

BibTeX entry:

@ARTICLE{jHuova10a,
  title = {A Note on Defect Theorems for 2-Dimensional Words and Trees},
  author = {Huova, Mari},
  journal = {Journal of Automata, Languages and Combinatorics},
  volume = {14},
  number = {3-4/2009},
  pages = {203–209},
  year = {2010},
  keywords = {Defect theorem, 2-dimensional words, trees},
}

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

Publication Forum rating of this publication: level 1

Edit publication