home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / theory / 1847 < prev    next >
Encoding:
Internet Message Format  |  1992-08-31  |  3.0 KB
  1. Path: sparky!uunet!wupost!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!ucbvax!IME.USP.BR!is
  2. From: is@IME.USP.BR (Imre Simon)
  3. Newsgroups: comp.theory
  4. Subject: Are there reductions from Hilbert's 10th problem?
  5. Message-ID: <9209010005.AA16295@bidu.ime.usp.br>
  6. Date: 1 Sep 92 01:02:05 GMT
  7. Sender: daemon@ucbvax.BERKELEY.EDU
  8. Reply-To: Imre Simon <is@ime.usp.br>
  9. Lines: 64
  10.  
  11. Reading a recent posting by Richard Beigel about Matijasevic, Hilbert, etc
  12. reminded me that quite recently I saw a very ingenious proof of the
  13. undecidability of a problem in the Theory of Finite Automata by Daniel Krob,
  14. <dk@litp.ibp.fr> in
  15.  
  16.       "The equality problem for rational series with multiplicities
  17.        in the tropical semiring is undecidable".
  18.  
  19. At the end of this note I give some details about the problem.
  20.  
  21. Krob's proof is achieved by a reduction from Hilbert's 10th problem,
  22. i.e. that of finding integer zeroes of multivariate polynomials with integer
  23. coefficients, whose undecidability has been proved by Matiasevic about 20
  24. years ago in what was considered as a major advance in the area. The use of
  25. Hilbert's 10th instead of some other more conventional undecidable problem,
  26. like the Post Correspondence Problem, seems very much necessary at this moment.
  27.  
  28. My question is this: does anyone know of other undecidable problems, in
  29. Theoretical Computer Science, apparently unrelated to multivariate
  30. polynomials, whose undecidability is established by a reduction from Hilbert's
  31. 10th problem?
  32.  
  33. I will be glad to post an abstract of the answers  I receive.
  34.  
  35. Imre Simon <is@ime.usp.br>
  36.  
  37. * * * * *
  38.  
  39. About the problem solved by Krob:
  40.  
  41. The problem is related to computations in the tropical semiring (consisting of
  42. the natural numbers extended with infinity and whose operations are minimum
  43. and addition; note that this is the usual semiring to compute shortest paths
  44. and that one does not have multiplication readily available in this
  45. structure).  I would be glad to give a precise statement of the problem for
  46. anyone who requests it.
  47.  
  48. The (previous) openness of this equivalence problem was reasonably well known
  49. in the area and as far I know an overwhelming majority thought that the
  50. problem would turn out to be decidable.
  51.  
  52. Krob's solution also implies the undecidability of another problem whose
  53. undecidability has been established by Oscar Ibarra, using a very elaborate
  54. reduction from the halting problem, and independently by L.P. Lisovik who used
  55. a reduction from the Post Correspondence Problem.
  56.  
  57. * * * * *
  58.  
  59. Other references:
  60.  
  61. O. Ibarra
  62. The unsolvability of the equivalence problem for \epsilon-free NGSM's with
  63. unary input (output) alphabet and applications.
  64. SIAM J. Comput., 7 (1978), 524-532
  65.  
  66. I. Simon
  67. Recognizable sets with multiplicities in the tropical semiring.
  68. in MFCS'88, Lect. Notes in Comp. Sci. 324, Springer, 1988, 107-120.
  69.  
  70. L.P. Lisovik
  71. The identity problem for regular events over the direct product of free and
  72. cyclic semigroups (in Ukranian).
  73. Dok. Akad. Nauk Ukraiinskoj RSR ser. A 6 (1979), 410-413.
  74. English translation by Andreas Weber <weber@psc.informatik.uni-frankfurt.de>
  75.