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

DOI10.1016/J.TCS.2011.09.022MaRDI QIDQ764304zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

pushdown automatoncontext-free sequencesubword complexity function

Mathematics Subject Classification ID

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

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)\)

Cites work

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

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?
• scientific article; zbMATH DE number 3861188 (Why is no real title available?)

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)