2010/10/26 by Arseny M. Shur, Shur, Arseny M.
Computer Science · Mathematics · #68Q70 68R15 05C50 #Advanced Combinatorial Mathematics #Coding theory and cryptography #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #cs.DM #cs.FL #math.CO #msc:05C50 #msc:68Q70 #msc:68R15 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1010.5456
41 page 1 figure, 1 table
arxiv created 2010/10/26 · openalex publication_date 2010/10/26 · arxiv updated 2010/10/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper is an extended abstract of the dissertation presented by the author for the doctoral degree in physics and mathematics (in Russia). The main characteristic studied in the dissertation is combinatorial complexity, which is a "counting" function associated with a language and returning the number of words of given length in this language. For several classes of languages, a variety of problems about combinatorial complexity and its connections to other parameters of languages are studied. A brief introduction to the topic and the formulations of results are presented. No proofs are given; instead, the papers containing the proofs are cited.