Franck Seynhaeve, Sophie Tison, Marc Tommasi, Ralf Treinen  @ NUS Home/Search
Context Related
| lri.fr/LRI/articles/tr...tcsgrid.ps.gz Cached: PS.gz PS PDF Image Update Help From: lri.fr/~treinen/publications (more) (Enter author homepages) |
Rate this article:      (best)Comment on this article |
Abstract: We prove three new undecidability results for computational mechanisms over finite trees: There is a linear, ultra-shallow, noetherian and strongly confluent rewrite system R such that the 9 8 -fragment of the first-order theory of one-step-rewriting by R is undecidable; the emptiness problem for tree automata with equality tests between cousins is undecidable; and the 9 8 - fragment of the first-order theory of set constraints with the union operator is undecidable. The common... (Update)
Context of citations to this paper: More
.... 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...
.... 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...
Cited by: More
The Undecidability of the First-Order Theories of One Step.. - Vorobyov (2002) (Correct)
On Rewrite Constraints and Context Unification - Niehren, Tison (2000) (Correct)
Weakly Regular Relations and Applications - Limet, Réty, Seidl (2001) (Correct)
Similar documents (at the sentence level):
6.2%: Grid Structures and Undecidable Constraint Theories - Seynhaeve, Tommasi, Treinen (1997) (Correct)
Active bibliography (related documents): More All
0.6: A Decision Algorithm for Stratified Context Unification - Schmidt-Schauß (2001) (Correct)
0.5: An Undecidable Fragment of the Theory of Set Constraints - Charatonik (1998) (Correct)
0.4: The Recognizability Problem for Tree Automata with.. - Bogaert, Seynhaeve.. (1999) (Correct)
Similar documents based on text: More All
0.6: Tree Automata With One Memory, Set Constraints and . . . - Comon, al. (2001) (Correct)
0.5: Homomorphisms and Concurrent Term Rewriting - Seynhaeve, Tison, Tommasi (1999) (Correct)
0.4: Set Constraints and Automata - Gilleron, Tison, Tommasi (1996) (Correct)
Related documents from co-citation: More All
4: Encompassment properties and automata with constraints (context) - Caron, Coquid'e et al. - 1993
3: Undecidability of the first-order theory of one-step right ground rewriting (context) - Marcinkowski - 1997
3: the decidability of ground reducibility (context) - Kaplan, Choquer - 1986
BibTeX entry: (Update)
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. http://citeseer.comp.nus.edu.sg/231181.html More
@misc{ seynhaeve97grid,
author = "F. Seynhaeve and M. Tommasi and R. Treinen",
title = "Grid structure and undecidable constraint theories",
text = "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.",
year = "1997",
url = "citeseer.comp.nus.edu.sg/231181.html" }
Citations (may not include all citations):259 Elements of the Theory of Computation (context) - Lewis, Papadimitriou - 1981
241 Decidability of Second-Order Theories and Automata on Infini.. (context) - Rabin - 1969
131 Set Based Program Analysis - Heintze - 1992
102 Tree automata techniques and applications - Comon, Dauchet et al. - 1997
94 A finite presentation theorem for approximating logic progra.. - Heintze, Jaffar - 1990
82 A Decision Procedure for a Class of Set Constraints - Heintze, Jaffar - 1990
71 The monadic second-order logic of graphs (context) - Courcelle - 1990
52 Decidability of systems of set constraints with negative con.. - Aiken, Kozen et al. - 1995
44 Set constraints with projections are in NEXPTIME - Charatonik, Pacholski - 1994
30 Equality and disequality constraints on direct subterms in t.. (context) - Bogaert, Tison - 1992
28 Information and Computation (context) - Comon, Haberstrau et al. - 1994
23 On equality up-to constraints over finite trees (context) - Niehren, Pinkal et al. - 1997
21 cleaning and symbolic constraints solving (context) - Caron, Comon et al. - 1994
20 The Classical Decision Problem (context) - orger, Gr et al. - 1997
19 The structure of the models of decidable monadic theories of.. - Seese - 1991
16 Laboratoire d'Informatique Fondamentale de Lille (context) - Mongy - 1981
15 Information and Computation (context) - Kozen - 1998
12 The first-order theory of one-step rewriting is undecidable (context) - Treinen - 1996
11 Some new decidability results on positive and negative set c.. (context) - Gilleron, Tison et al. - 1994
9 Monadic second order definable relation on the binary tree (context) - auchli, Savioz - 1987
9 Undecidability of the first order theory of one-step right g.. (context) - Marcinkowski - 1997
8 The first-order theory of one-step rewriting in linear noeth.. - Vorobyov - 1997
3 The first-order theory of linear one-step rewriting is undec.. - Treinen - 1998
3 The recognizability problem for tree automata with compariso.. - Bogaert, Seynhaeve et al. - 1999
2 An undecidable result for automata with equality tests (context) - Seynhaeve, Tison et al. - 1996
2 Deciding the satisfiability of quantifier free formulae on o.. (context) - Caron, Seynhaeve et al. - 1999
1 The undecidability of the first order theories of one-step r.. - Vorobyov - 1998
1 Contraintes Ensemblistes D'efinies et Co-D'efinies (context) - Talbot - 1998
1 Automates et Contraintes (context) - Seynhaeve - 1999
1 invited lecture (context) - Thomas - 1991
1 An undecidable fragment of the theory of set constraints - Charatonik - 1998
1 Information and Computation (context) - Gilleron, Tison et al. - 1999
The graph only includes citing articles where the year of publication is known.
Documents on the same site (http://www.lri.fr/~treinen/publications.html): More
Records for Logic Programming - Smolka, Treinen (1994) (Correct)
Constraint Deduction in an Interval-based Temporal Logic - Jana Koehler, Ralf Treinen (1993) (Correct)
A New Method for Undecidability Proofs of First Order Theories - Treinen (1992) (Correct)
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.