On the complexity of a family of \(k\)-context-free sequences

DOI10.1016/j.tcs.2011.09.022zbMath1239.68057OpenAlexW2026402057MaRDI QIDQ764304

Publication date: 13 March 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.09.022

zbMATH Keywords

pushdown automaton context-free sequence subword complexity function

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45) Descriptive complexity and finite models (68Q19)

Related Items (2)

When is an automatic set an additive basis? ⋮ On the computational complexity of algebraic numbers: the Hartmanis–Stearns problem revisited

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
On the regular structure of prefix rewriting
On some questions regarding \(k\)-regular and \(k\)-context-free sequences
On complexity functions of infinite words associated with generalized Dyck languages
The theory of ends, pushdown automata, and second-order logic
The ring of \(k\)-regular sequences
Subword complexities of various classes of deterministic developmental languages without interactions
Complexity and special factors
Complexity of sequences and dynamical systems
On the complexity of infinite sequences
The ring of \(k\)-regular sequences. II.
Generalization of automatic sequences for numeration systems on a regular language
On infinite transition graphs having a decidable monadic theory
Substitution dynamical systems on infinite alphabets
On the complexity of infinite words generated by countable \(q\)-automata
Arithmetics properties of substitutions and infinite automata
The Kolmogorov complexity of infinite words
Integers with an average sum of digits
On the distribution in residue classes of integers with a fixed sum of digits
On the complexity of algebraic numbers. I: Expansions in integer bases
Complexité des facteurs des mots infinis engendrés par morphismes itérés
Drunken man infinite words complexity
On the arithmetic structure of the integers whose sum of digits is fixed
Automatic Sequences
Substitutions par des motifs en dimension 1
Three models for the description of language
On the Recognition of Primes by Automata
A Remark on Acceptable Sets of Numbers
Unrecognizable Sets of Numbers
Uniform tag sequences

This page was built for publication: On the complexity of a family of \(k\)-context-free sequences