Decimations of languages and state complexity

DOI10.1016/J.TCS.2009.02.024MaRDI QIDQ1019721zbMATH OpenOpenAlexFDO

Authors Dalia Krieger, Avery Miller, Narad Rampersad, B. Ravikumar, Jeffrey 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 languagedeterministic finite automatonstate complexitydecimationslender language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 2068872
• State Complexity of Deletion
• Filtrations of formal languages by arithmetic progressions
• Operational State Complexity under Parikh Equivalence
• State complexity of some operations on binary regular languages

Cites work

• scientific article; zbMATH DE number 51878 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Abstract numeration systems on bounded languages and multiplication by a constant
• Automatic Sequences
• Construction of regular languages and recognizability of polynomials
• Generalization of automatic sequences for numeration systems on a regular language
• Numeration systems on a regular language
• Numeration systems, linear recurrences, and regular sets
• On a conjecture about slender context-free languages
• On lengths of words in context-free languages
• Operations preserving regular languages
• Partial orders on words, minimal elements of regular languages, and state complexity
• The set of minimal words of a context-free language is context-free
• Thin and slender languages
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION

Cited in

(5)

• State complexity of the concatenation of regular tree languages
• Decimation and interleaving operations in one-sided symbolic dynamics
• The range of state complexities of languages resulting from the cut operation
• scientific article; zbMATH DE number 2201359 (Why is no real title available?)
• Filtrations of formal languages by arithmetic progressions

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

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