Name
Abstract | ||
|---|---|---|
The aim of this paper is the study of a procedure S given in [11, 13]. We prove that this procedure can compute the closure of the star of a closed recognizable set of words if and only if this closure is also recognizable. This necessary and sufficient condition gives a semi algorithm for the Star Problem. As intermediary results, using S, we give new proofs of some known results.
In the last part, we compare the power of S with the rank notion introduced by Hashigushi [9]. Finally, we characterize the recognizability of the closure of star of recognizable closed sets of words using this rank notion.
|
Year | DOI | Venue |
|---|---|---|
1995 | 10.1007/3-540-60084-1_64 | ICALP |
Keywords | Field | DocType |
partial commutations | Discrete mathematics,Combinatorics,Computer science,Mathematical proof,If and only if | Conference |
Volume | ISSN | ISBN |
944 | 0302-9743 | 3-540-60084-1 |
Citations | PageRank | References |
3 | 0.49 | 7 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yves Métivier | 1 | 594 | 53.83 |
| Gwénaël Richomme | 2 | 136 | 18.10 |
| Pierre-andré Wacrenier | 3 | 766 | 36.69 |