Seynhaeve, F., Tommasi, M., and Treinen, R. (1997), Grid structure and undecidable constraint theories, in "TAPSOFT'97," Lecture Notes in Computer Science, Vol. 1214, pp. 357--368, Springer-Verlag, Berlin. @ NUS Home/Search Document Details and Download
Summary Related Articles Check |
This paper is cited in the following contexts:
Weakly Regular Relations and Applications - Limet, Réty, Seidl (2001) (Correct)
....order theory over the universe of ground terms that uses the only predicate symbol , where x y means x rewrites into y by one step. It has been shown undecidable in [16] Sharper undecidability results have been obtained for some subclasses of rewrite systems, about the 9 8 fragment [15, 12] and the 9 8 9 fragment [17] It has been shown decidable in the case of unary signatures [6] in the case of linear rewrite systems whose left and right members do not share any variables [2] 7 , for the positive existential fragment [13] for the whole existential fragment in the ....
F. Seynhaeve, M. Tommasi, and R. Treinen. Grid Structures and Undecidable Constraint Theories. In Proceedings of 6th Colloquium on Trees in Algebra and Programming, volume 1214 of LNCS, pages 357-368. Springer-Verlag, 1997.
The Undecidability of the First-Order Theories of One Step.. - Vorobyov (1998) (1 citation) (Correct)
....systems. As a methodological advantage of the proof presented here let us mention the use of reduction from the well known undecidable halting problem for the 1 i.e. containing repeated variable occurrences on the left (or right) hand side 2 Later this was improved to linear shallow systems (Seynhaeve, Tommasi Treinen 1997), but still non terminating with rules t t. 4 two counter machines (Minsky 1961, Minsky 1967, Lewis 1979) Note that (Marcinkowski 1997) used a rather complicated home made undecidability problem in his proof (the details has not yet been published) The main results of the paper are ....
....Systems) There exists (and can be explicitly presented) a finite linear canonical term rewriting system with undecidable 98 theory of one step rewriting. 2 11 For comparison, Treinen 1996) proved weak undecidability for 998 theories in non terminating, non linear, non confluent systems, and (Seynhaeve et al. 1997) proved weak undecidability for 998 theories in non terminating (with rules t t) non confluent but linear and shallow systems. Strong undecidability proofs appeared only in (Vorobyov 1995, Vorobyov 1997) 12 7 Minsky s Two Register Machine Our undecidability proof is by reduction from the ....
Seynhaeve, F., Tommasi, M. & Treinen, R. (1997), Grid structure and undecidable constraint theories, in `TAPSOFT'97', Vol. 1214 of Lect. Notes Comput. Sci., Springer-Verlag, pp. 357--368.
On Rewrite Constraints and Context Unification - Niehren, Tison (2000) (1 citation) Self-citation (Treinen) (Correct)
....project was to show decidability of the rst order theory of these constraints since such a result would have allowed to generalize known decidability results in rewrite theory. However, undecidability of the 8 9 fragment could be shown even for very simple classes of rewrite systems [19,20,10,18]. The question of decidability of the purely existential fragment of positive and negative rewrite constraints remains open, even though some cases for restricted classes of rewrite systems are solved [2,8] It has been shown in [12] that satis ability of RC can be expressed as satis ability of ....
F. Seynhaeve, M. Tommasi, and R. Treinen. Grid structures and undecidable constraint theories. In Theory and Practice of Software Development, volume 1214 of LNCS, pages 357-368, 1997. Extended Version to appear in Theoretical Computer Science.
The Undecidability of the First-Order Theories of One Step.. - Vorobyov (2002) (1 citation) (Correct)
No context found.
Seynhaeve, F., Tommasi, M., and Treinen, R. (1997), Grid structure and undecidable constraint theories, in "TAPSOFT'97," Lecture Notes in Computer Science, Vol. 1214, pp. 357--368, Springer-Verlag, Berlin.
The Undecidability of the First-Order Theories of One Step.. - Vorobyov (2002) (1 citation) (Correct)
No context found.
F. Seynhaeve, M. Tommasi, and R. Treinen. Grid structure and undecidable constraint theories. In TAPSOFT'97, volume 1214 of Lect. Notes Comput. Sci., pages 357-368. Springer-Verlag, 1997.
Online articles have much greater impact More about CiteSeer.IST at NUS Add search form to your site Submit documents Feedback
CiteSeer.IST at NUS - Copyright Penn State and NEC. Hosted by the School of Computing, National University of Singapore.