Combinatorial Complexity of Regular Languages

DOI10.1007/978-3-540-79709-8_30MaRDI QIDQ3503647zbMATH OpenOpenAlexFDO

Authors Arseny M. Shur

Publication date 5 June 2008

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-79709-8_30

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Combinatorics on words (68R15)

Recommendations

• Growth rates of complexity of power-free languages
• Growth rates of power-free languages
• Factorial Languages of Low Combinatorial Complexity
• Towards a theory of complexity of regular languages
• Automaticity. I: Properties of a measure of descriptional complexity

Cited in

(22)

• Growth of power-free languages over large alphabets
• The carry propagation of the successor function
• In Search of Most Complex Regular Languages
• Complexity Results and the Growths of Hairpin Completions of Regular Languages (Extended Abstract)
• Cardinality estimates for some classes of regular languages
• Efficient Enumeration of Regular Languages
• Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time
• Two-Sided Bounds for the Growth Rates of Power-Free Languages
• Regular languages and partial commutations
• Normal forms of random braids.
• scientific article; zbMATH DE number 1134630 (Why is no real title available?)
• Growth properties of power-free languages
• Rational transductions and complexity of counting problems
• Binary words avoiding the pattern AABBCABBA
• On the growth rates of complexity of threshold languages
• scientific article; zbMATH DE number 4187790 (Why is no real title available?)
• A new hierarchy for automaton semigroups
• A closer look at the expressive power of logics based on word equations
• A graph-theoretic proof of Cobham's dichotomy for automatic sequences
• Branching frequency and Markov entropy of repetition-free languages
• On the penetration distance in Garside monoids
• Growth rates of complexity of power-free languages

This page was built for publication: Combinatorial Complexity of Regular Languages

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