Name
Abstract | ||
|---|---|---|
A variant of Post's Correspondence Problem is considered where two different index words are allowed provided that one of them can be obtained from the other by permuting a fixed number of subwords. It is shown that this variant is undecidable. Post's Correspondence Problem is also extended to circular words, doubly infinite words and doubly infinite powers of words, and shown to be undecidable in all these extensions. |
Year | DOI | Venue |
|---|---|---|
1983 | 10.1007/BF00290732 | Acta Inf. |
Keywords | Field | DocType |
Information System,Operating System,Data Structure,Communication Network,Information Theory | Information system,Information theory,Data structure,Discrete mathematics,Combinatorics,Formal language,Permutation,Correspondence problem,Mathematics,Combinatorics on words,Undecidable problem | Journal |
Volume | Issue | ISSN |
19 | 4 | 0001-5903 |
Citations | PageRank | References |
9 | 1.07 | 6 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Keijo Ruohonen | 1 | 151 | 22.20 |