Factorial languages whose growth function is quadratically upper bounded

DOI10.1016/0020-0190(89)90228-7zbMath0672.68034OpenAlexW2048250184MaRDI QIDQ1120288

Stefano Varricchio, Aldo De Luca

Publication date: 1989

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90228-7

zbMATH Keywords

growth functionfactorial languagefactor monoidsubword-complexityweakly-permutable

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Factorials, binomial coefficients, combinatorial functions (05A10) Combinatorics on words (68R15) Formal languages and automata (68Q45)

Related Items

Pentagonal chains and annuli as models for designing nanostructures from cages, Factorial languages with quadratically upper bounded growth functions and nonlinearly upper bounded subword complexities, Properties of infinite words : Recent results, A finiteness condition for semigroups generalizing a theorem of Hotzel, Stefano Varricchio (1960-2008), A note on \(\omega\)-permutable semigroups

Cites Work

• Unnamed Item
• Unnamed Item
• On the Burnside problem for semigroups
• Permutation properties and the Fibonacci semigroup
• Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups
• On the factors of the Thue-Morse word on three symbols
• A combinatorial theorem on $p$-power-free words and an application to semigroups