D. Lugiez, J. L. Moysset  @ NUS Home/Search
Context Related
| loria.fr/~lugiez/Publis/cpac.ps.gz Cached: PS.gz PS PDF Image Update Help From: loria.fr/~lugie...al_page_english (more) (Enter author homepages) |
Rate this article:      (best)Comment on this article |
Abstract: this paper we consider particular equational formulae where equality =AC is the congruence induced by a set of associative-commutative axioms. The formulae we are interested in have the form t 6= AC t 1 : : : t 6= AC t n and are usually known as complement problems. To solve a complement problem is to find an instance of t which is not an instance of any t i modulo associativity-commutativity. We give a decision procedure based on tree automata which solves these formulae when all the t i (Update)
Context of citations to this paper: More
.... problem for linear terms was proved decidable by Lassez and Marriott [LM87] and the AC complement problem by Lugiez and Moysset [LM94] The reachability problem is de ned in Exercise 16. It is well known that this problem is undecidable in general. It is decidable for...
Cited by: More
Tree Automata Techniques and Applications -.. - Comon, Dauchet.. (1998) (Correct)
Tree Automata Techniques and Applications -.. - Comon, Dauchet.. (Correct)
Tree Automata Techniques and Applications -.. - Comon, Dauchet.. (1998) (Correct)
Active bibliography (related documents): More All
0.5: A Methodological View of Constraint Solving - Comon, al. (1997) (Correct)
0.5: Handling Equality in Logic Programs via Basic Folding - Degtyarev, Voronkov (1998) (Correct)
0.3: Feature Trees over Arbitrary Structures - Treinen (1997) (Correct)
Similar documents based on text: More All
0.4: The Complement Problem in Associative-Commutative Theories - Kounalis, Lugiez, Pottier (Correct)
0.0: Automata-Driven Automated Induction - Bouhoula, Jouannaud (1996) (Correct)
0.0: On n-Syntactic Equational Theories - Boudet, Contejean (1992) (Correct)
Related documents from co-citation: More All
15: Completion of rewrite systems with membership constraints - Comon - 1992
14: nite tree automata (context) - Seidl, of - 1989
11: Automata-driven automated induction - Bouhoula, Jouannaud - 1996
BibTeX entry: (Update)
Denis Lugiez and Jean-Luc Moysset. Tree automata help one to solve equational formulae in ac-theories. Journal of Symbolic Computation, 18(4):297-- 318, 1994. http://citeseer.comp.nus.edu.sg/131847.html More
@misc{ lugiez94tree,
author = "D. Lugiez and J. Moysset",
title = "Tree automata help one to solve equational formulae in ac-theories",
text = "Denis Lugiez and Jean-Luc Moysset. Tree automata help one to solve equational
formulae in ac-theories. Journal of Symbolic Computation, 18(4):297-- 318,
1994.",
year = "1994",
url = "citeseer.comp.nus.edu.sg/131847.html" }
Citations (may not include all citations):118 Complete axiomatization of the algebra of finite (context) - Maher - 1988
113 Akad'emiai Kiad'o (context) - G'ecseg, Steinby - 1984
34 Automatic proofs by induction in theories without constructo.. (context) - Jouannaud, Kounalis - 1989
30 Equality and disequality constraints on direct subterms in t.. (context) - Bogaert, Tison - 1992
20 groundreducibility and their complexity (context) - Kapur, Narendran et al. - 1991
20 Feature automata and recognizable sets of feature trees - Joachim, Andreas - 1993
6 Elimination of negation in term algebra - Lassez, Maher et al. - 1991
3 A new method for undecidability proofs of first order theori.. - Ralf - 1992
2 Explicit representation of terms defined by counter examples (context) - Jean-Louis, Marriot - 1986
1 Complement problems and tree automata in AC-like theories (context) - Denis, Jean-Luc - 1993
The graph only includes citing articles where the year of publication is known.
Documents on the same site (http://www.loria.fr/~lugiez/personal_page_english.html):
A Good Class of Tree Automata and An Application to Inductive.. - Lugiez (Correct)
Set Operations for Recurrent Term Schematizations - Amaniss, Hermann, Lugiez (1997) (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.