Decimations of languages and state complexity
From MaRDI portal
Publication:1019721
DOI10.1016/j.tcs.2009.02.024zbMath1168.68026MaRDI QIDQ1019721
Avery Miller, Narad Rampersad, Jeffrey O. Shallit, Dalia Krieger, Bala Ravikumar
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
context-free language; state complexity; deterministic finite automaton; decimation; slender language
68Q45: Formal languages and automata
Related Items
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item