Palindromic complexity of trees

DOI10.1007/978-3-319-21500-6_12MaRDI QIDQ3451098zbMATH OpenOpenAlexFDO

Authors Srečko Brlek, Nadia Lafrenière, Xavier Provençal

Publication date 10 November 2015

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.02695

zbMATH Keywords

languagepalindromic complexitySidon setstreeswords

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Combinatorics on words (68R15)

Abstract: We consider finite trees with edges labeled by letters on a finite alphabet $varSigma$. Each pair of nodes defines a unique labeled path whose trace is a word of the free monoid $varSigm{a}^{\ast }$. The set of all such words defines the language of the tree. In this paper, we investigate the palindromic complexity of trees and provide hints for an upper bound on the number of distinct palindromes in the language of a tree.

Recommendations

• Tight bound for the number of distinct palindromes in a tree
• Palindromes in starlike trees
• Total palindrome complexity of finite words
• Palindrome complexity.
• Properties of palindromes in finite words

Cites work

• A \(d\)-dimensional extension of Christoffel words
• Complexity and palindromic defect of infinite words
• Episturmian words and some constructions of de Luca and Rauzy
• Episturmian words: a survey
• Geometric palindromic closure
• How many squares can a string contain?
• scientific article; zbMATH DE number 1024080 (Why is no real title available?)
• On a Problem of Sidon in Additive Number Theory, and on some Related Problems
• ON THE PALINDROMIC COMPLEXITY OF INFINITE WORDS
• Palindrome complexity.
• Palindromic language of thin discrete planes
• Proof of the Brlek-Reutenauer conjecture
• Singular continuous spectrum for palindromic Schrödinger operators
• Sturmian words: structure, combinatorics, and their arithmetics
• The maximum number of squares in a tree
• Tilings and rotations on the torus: A two-dimensional generalization of Sturmian sequences

Cited in

(11)

• Total palindrome complexity of finite words
• String powers in trees
• Palindrome complexity.
• String covers of a tree
• scientific article; zbMATH DE number 5501412 (Why is no real title available?)
• Palindromes in starlike trees
• Palindromic characteristic of committed graphs and some model theoretic properties
• Tight bound for the number of distinct palindromes in a tree
• Palindromic complexity of codings of rotations
• String covers of a tree revisited
• Double-ended palindromic trees in linear time

This page was built for publication: Palindromic complexity of trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3451098)