Skip to main navigation Skip to search Skip to main content

Palindromic language of thin discrete planes

  • CNRS
  • Université Savoie Mont Blanc

Research output: Contribution to journal › Journal Article › peer-review

1 Citation (Scopus)

Abstract

We work on the Réveillès hyperplane P(v,0,ω) with normal vector v∈Rd, shift μ = 0 and thickness ω∈R. Such a hyperplane is connected as soon as ω is greater than some value Ω(v,0), called the connecting thickness of v with null shift. In the case where v satisfies the so called Kraaikamp and Meester criterion, at the connecting thickness the hyperplane has very specific properties. First of all the adjacency graph of the voxels forms a tree. This tree appeared in many works both in discrete geometry and in discrete dynamical systems. In addition, it is well known that for a finite coding of length n of discrete lines, the number of palindromes in the language is exactly n + 1. We extend this notion of language to labeled trees and we compute the number of distinct palindromes. In fact for our voxel adjacency trees with n letters we show that the number of palindromes in the language is also n + 1. This result establishes a first link between combinatorics on words, palindromic languages, voxel adjacency trees and connecting thickness of Réveillès hyperplanes. It also provides a better understanding of the combinatorial structure of discrete planes.

Original languageEnglish
Pages (from-to)101-108
Number of pages8
JournalTheoretical Computer Science
Volume624
DOIs
Publication statusPublished - 18 Apr 2016
Externally publishedYes

Keywords

  • Discrete planes
  • Palindromic languages
  • Voxel adjacency trees

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Palindromic language of thin discrete planes'. These topics are generated from the title and abstract of the publication. Together, they form a unique fingerprint.

Cite this