Anne-Cécile Caron, Hubert Comon, Jean-Luc Coquidé, Max Dauchet, Florent Jacquemard  @ NUS Home/Search
Context
Related
| lifl.fr/pub/project...icalp94long.ps.Z Cached: PS.gz PS PDF Image Update Help From: fermivista.math.jus...ftp.lifl.fr (more) (Enter author homepages) |
Rate this article:      (best)Comment on this article |
Abstract: We define a new class of tree automata which generalizes both the encompassment automata of [3] and the automata with tests between brothers of [2]. We give a pumping lemma for these automata, which implies that the emptiness of the corresponding language is decidable. Then, we show how to decide emptiness by means of a "cleaning" algorithm, which leads to more effective decision procedures. Introduction Ground reducibility of a term t with respect to a term rewriting system R is the ... (Update)
Active bibliography (related documents): More All
0.3: Summary of the Lecture - The Course (Correct)
0.3: Ground Reducibility is EXPTIME-complete - Hubert Comon (1997) (Correct)
0.3: Ground Reducibility and Automata with Disequality Constraints - Hubert Comon (1994) (Correct)
Similar documents based on text: More All
0.4: The Undecidability of the First-Order Theories of One Step.. - Vorobyov (1998) (Correct)
0.3: Exercise 14 - Use The Pumping (Correct)
0.3: Unification in Extensions of Shallow Equational Theories - Jacquemard, Meyer, Weidenbach (1998) (Correct)
BibTeX entry: (Update)
@misc{ caron-pumping,
author = "Anne-Cécile Caron and Hubert Comon and Jean-Luc Coquidé and
Max Dauchet and Florent Jacquemard",
title = "Pumping, Cleaning and Symbolic Constraints Solving",
url = "citeseer.comp.nus.edu.sg/140262.html" }
Citations (may not include all citations):121 Handbook of Theoretical Computer Science (context) - Dershowitz, Jouannaud - 1990
118 Complete axiomatizations of the algebras of finite (context) - Maher - 1988
51 Proof by consistency in equational theories (context) - Bachmair - 1988
50 Semantic confluence tests and completion method (context) - Plaisted - 1985
41 Encompassment properties and automata with constraints (context) - Caron, Coquid'e et al. - 1993
41 Encompassment properties and automata with constraints (context) - Caron, Coquid'e et al. - 1993
34 Automatic proofs by induction in theories without constructo.. (context) - Jouannaud, Kounalis - 1989
31 On sufficient-completeness and related properties of term re.. (context) - Kapur, Narendran et al. - 1987
30 Equality and disequality constraints on direct subterms in t.. (context) - Bogaert, Tison - 1992
20 Equational formulas on order-sorted algebras (context) - Comon - 1990
16 Laboratoire d'Informatique Fondamentale de Lille (context) - Mongy, reconnaissables et al. - 1981
11 Narrowing based procedures for equational disunification (context) - Fern'andez - 1992
10 Structural complexity of classes of tree languages (context) - Dauchet, Tison - 1992
6 Unification et disunification (context) - Comon - 1988
5 reducibility in term rewriting systems (context) - Kounalis, the et al. - 1992
1 Order-sorted unification with term declarations (context) - Socher-Ambrosius - 1993
Documents on the same site (http://fermivista.math.jussieu.fr/ftp/ftp.lifl.fr.html): More
Complex Strategies in the Iterated Prisoner's Dilemma - Delahaye, Mathieu (1995) (Correct)
How to Use Cycles for Logical Compilation - Roussel, Mathieu (1996) (Correct)
A Framework for Cooperation in Hierarchical Multi-Agent Systems - Bensaid, MATHIEU (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.