On the complexity of a family of k-context-free sequences

DOI10.1016/J.TCS.2011.09.022zbMATH Open1239.68057OpenAlexW2026402057MaRDI QIDQ764304FDOQ764304

Authors: Marion Le Gonidec

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

Recommendations

On some questions regarding \(k\)-regular and \(k\)-context-free sequences
On the complexity of finite sequences over a finite set
A complexity measure for families of binary sequences
The subword complexity of a two-parameter family of sequences
On Lempel-Ziv Complexity of Sequences
On the \(k\)-abelian complexity of the Cantor sequence
On the Kolmogorov-Chaitin Complexity for short sequences
The characterization of \(N\)-écritures and applications to the study of sequences of finally \(n+c^{st}\) complexity
On the complexity function for sequences which are not uniformly recurrent
On linear complexity of sequences over \(\text{GF}(2^n)\)

zbMATH Keywords

pushdown automaton context-free sequence subword complexity function

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

Context-free sequences
On the computational complexity of algebraic numbers: the Hartmanis-Stearns problem revisited
When is an automatic set an additive basis?
Title not available (Why is that?)

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

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