Name
Abstract | ||
|---|---|---|
Starting from six kinds of periodicity of words we define six sets of words which are primitive in different senses and we investigate their relationships. We show that only three of the sets are external Marcus contextual languages with choice but none of them is an external contextual language without choice or an internal contextual language. For the time complexity of deciding any of our sets by one-tape Turing machines, n(2) is a lower bound and this is optimal in two cases. The notions of roots and degrees of words and languages, which are strongly connected to periodicity and primitivity, are also considered, and we show that there can be an arbitrarily large gap between the complexity of a language and that of its roots. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1002/malq.200610030 | MATHEMATICAL LOGIC QUARTERLY |
Keywords | Field | DocType |
periodicity of words,primitivity of words,Marcus contextual languages,roots of words and languages,computational complexity of languages | Discrete mathematics,Combinatorics,Upper and lower bounds,Turing machine,Strongly connected component,Time complexity,Arbitrarily large,Mathematics | Journal |
Volume | Issue | ISSN |
53 | 1 | 0942-5616 |
Citations | PageRank | References |
11 | 0.86 | 1 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Masami Ito | 1 | 299 | 66.19 |
| Gerhard Lischke | 2 | 42 | 8.42 |