Counting Finite Languages by Total Word Length

DOI10.1515/INTEG.2011.068MaRDI QIDQ3108546zbMATH OpenOpenAlexFDO

Authors Stefan Gerhold

Publication date 4 January 2012

Published in Integers (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1001.4392

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

asymptoticsfinite alphabetfinite languagesgenerating functionlength of wordssaddle point methodsets of words

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16) Combinatorics on words (68R15)

Abstract: We investigate the number of sets of words that can be formed from a finite alphabet, counted by the total length of the words in the set. An explicit expression for the counting sequence is derived from the generating function, and asymptotics for large alphabet respectively large total word length are discussed. Moreover, we derive a Gaussian limit law for the number of words in a random finite language.

Recommendations

• On lengths of words in context-free languages
• Context-Free Languages of Countable Words
• scientific article; zbMATH DE number 1560303
• On counting functions of languages
• Separating the words of a language by counting factors
• Counting subwords and regular languages
• Linear languages of finite and infinite words
• Comparing consecutive letter counts in multiple context-free languages
• Count of primitive words

Cited in

(10)

• Enumerating totally clean words
• On the number of words with restrictions on the number of symbols
• Difference Equation Theory Meets Mathematical Finance
• Enumeration of words by the sum of differences between adjacent letters
• Counting occurrences for a finite set of words: an inclusion-exclusion approach
• scientific article; zbMATH DE number 1560303 (Why is no real title available?)
• How to make Dupire's local volatility work with jumps
• scientific article; zbMATH DE number 238432 (Why is no real title available?)
• Comparing consecutive letter counts in multiple context-free languages
• On cardinality of bigram languages

This page was built for publication: Counting Finite Languages by Total Word Length

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