6533b852fe1ef96bd12aada1

RESEARCH PRODUCT

On the least number of palindromes contained in an infinite word

Gabriele FiciLuca Q. Zamboni

subject

FOS: Computer and information sciencesGeneral Computer ScienceDiscrete Mathematics (cs.DM)Formal Languages and Automata Theory (cs.FL)Computer Science - Formal Languages and Automata Theory0102 computer and information sciences68R1501 natural sciencesTheoretical Computer ScienceCombinatorics[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]FOS: MathematicsMathematics - CombinatoricsPalindromes0101 mathematicsComputingMilieux_MISCELLANEOUSMathematicsCombinatorics on wordDiscrete mathematics010102 general mathematicsPalindromeCombinatorics on words010201 computation theory & mathematicsCombinatorics (math.CO)AlphabetWord (group theory)Computer Science::Formal Languages and Automata TheoryComputer Science - Discrete Mathematics

description

We investigate the least number of palindromic factors in an infinite word. We first consider general alphabets, and give answers to this problem for periodic and non-periodic words, closed or not under reversal of factors. We then investigate the same problem when the alphabet has size two.

yearjournalcountryeditionlanguage
2013-01-15
10.1016/j.tcs.2013.02.013http://arxiv.org/abs/1301.3376