ON SIMPLEST POSSIBLE SOLUTIONS FOR POST CORRESPONDENCE PROBLEMS

Authors
MATEESCU A SALOMAA A
Citation
A. Mateescu et A. Salomaa, ON SIMPLEST POSSIBLE SOLUTIONS FOR POST CORRESPONDENCE PROBLEMS, Acta informatica, 30(5), 1993, pp. 441-457
Citations number
5
Categorie Soggetti
Information Science & Library Science","Computer Applications & Cybernetics
Journal title
Acta informatica → ACNP
ISSN journal
00015903
Volume
30
Issue
5
Year of publication
1993
Pages
441 - 457
Database
ISI
SICI code
0001-5903(1993)30:5<441:OSPSFP>2.0.ZU;2-L
Abstract
We investigate the simplicity of solutions for instances of the Post C orrespondence Problem, from the point of view of both index words and terminal words. This leads to the notion of a mixed primality type of an instance. Our main result gives an exhaustive characterization of m ixed primality types.