Search

We prove some new theorems in additive number theory, using novel techniques from automata theory and formal languages. As an example of our method, we prove that every natural number > 2 5 is the sum of at most three natural numbers whose base- 2 representation has an equal number of 0 's and 1 's. [ABSTRACT FROM AUTHOR]

A filtration of a formal language L by a sequence s maps L to the set of words formed by taking the letters of words of L indexed only by s. We consider the languages resulting from filtering by all arithmetic progressions. If L is regular, it is easy to see that only finitely many distinct languages result; we give bounds on the number of distinct languages in terms of the state complexity of L. By contrast, there exist CFL's that give infinitely many distinct languages as a result. We use our technique to show that two related operations, including diag (which extracts the diagonal of words of square length arranged in a square array), preserve regularity but do not preserve context-freeness. [ABSTRACT FROM AUTHOR]

Abstract: The cross-section enumeration problem is to list all words of length in a regular language in lexicographical order. The enumeration problem is to list the first words in according to radix order. We present an algorithm for the cross-section enumeration problem that is linear in , where is the output size. We provide a detailed analysis of the asymptotic running time of our algorithm and that of known algorithms for both enumeration problems. We discuss some shortcomings of the enumeration algorithm found in the Grail computation package. In the practical domain, we modify Mäkinen’s enumeration algorithm to get an algorithm that is usually the most efficient in practice. We performed an extensive performance analysis of the new and previously known enumeration and cross-section enumeration algorithms and found when each algorithm is preferable. [Copyright &y& Elsevier]