Abstract | ||
---|---|---|
We solve a conjecture of J. Shallit related to the automaticity function of a unary language, or equivalently to the first occurrence function in a symbolic sequence. The answer is negative: the conjecture is false, but it can be corrected by changing the constant involved. The proof is based on a study of paths in the Rauzy graphs associated to the sequence. |
Year | DOI | Venue |
---|---|---|
1997 | 10.1007/3-540-63165-8_223 | ICALP |
Keywords | Field | DocType |
j. shallit | Discrete mathematics,Graph,Combinatorics,Formal language,Unary language,Finite-state machine,Automaticity,Regular language,Conjecture,Mathematics,Fibonacci number | Conference |
Volume | ISSN | ISBN |
1256 | 0302-9743 | 3-540-63165-8 |
Citations | PageRank | References |
4 | 0.55 | 3 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Julien Cassaigne | 1 | 282 | 40.80 |