Decimations of languages and state complexity

DOI10.1016/J.TCS.2009.02.024zbMath1168.68026OpenAlexW2026951311MaRDI QIDQ1019721

Avery Miller, Bala Ravikumar, Dalia Krieger, Narad Rampersad, Jeffrey O. Shallit

Publication date: 4 June 2009

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

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

zbMATH Keywords

context-free languagestate complexitydeterministic finite automatondecimationslender language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (2)

State complexity of the concatenation of regular tree languages ⋮ Decimation and interleaving operations in one-sided symbolic dynamics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Partial orders on words, minimal elements of regular languages, and state complexity
• Numeration systems, linear recurrences, and regular sets
• On a conjecture about slender context-free languages
• The set of minimal words of a context-free language is context-free
• On lengths of words in context-free languages
• Generalization of automatic sequences for numeration systems on a regular language
• Construction of regular languages and recognizability of polynomials
• Thin and slender languages
• Operations preserving regular languages
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
• Automatic Sequences
• Numeration systems on a regular language

This page was built for publication: Decimations of languages and state complexity