Abstract | ||
---|---|---|
Let Q be the set of primitive words over a finite alphabet having at least two letters. We prove that Q has two rather strong context-free-like properties. The first one is that Q satisfies the nonempty, strong variant of Bader and Moura's iteration condition, and the second one is that intersecting Q with any member of a special, infinite family of regular languages, we get a context-free language. We also present two further related results. It remains an unsolved problem whether Q is non-context-free (we conjecture this). |
Year | DOI | Venue |
---|---|---|
1993 | 10.1007/3-540-57163-9_15 | FCT |
Keywords | Field | DocType |
primitive words,formal language,context free language,regular language,satisfiability | Discrete mathematics,Context-free language,Combinatorics,Formal language,Computer science,Abstract family of languages,Cone (formal languages),Regular language,Picture language,Conjecture,Language primitive | Conference |
ISBN | Citations | PageRank |
3-540-57163-9 | 12 | 0.90 |
References | Authors | |
7 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Pál Dömösi | 1 | 39 | 16.25 |
Sándor Horváth | 2 | 45 | 9.84 |
Masami Ito | 3 | 299 | 66.19 |
L. Kászonyi | 4 | 64 | 9.49 |
M. Katsura | 5 | 58 | 10.49 |