6533b7dcfe1ef96bd1273331
RESEARCH PRODUCT
STURMIAN WORDS AND AMBIGUOUS CONTEXT-FREE LANGUAGES
Filippo MignosiFilippo Mignosisubject
CombinatoricsDiscrete mathematicsRational numberCombinatorics on wordsNumber theoryContext-free languageComputer Science (miscellaneous)Generating functionSturmian wordNatural densityTranscendental numberMathematicsdescription
If x is a rational number, 0<x≤1, then A(x)c is a context-free language, where A(x) is the set of factors of the infinite Sturmian words with asymptotic density of 1’s smaller than or equal to x. We also prove a “gap” theorem i.e. A(x) can never be an unambiguous co-context-free language. The “gap” theorem is established by proving that the counting generating function of A(x) is transcendental. We show some links between Sturmian words, combinatorics and number theory.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1990-09-01 | International Journal of Foundations of Computer Science |