Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. E-unification by mea ...
Article

E-unification by means of tree tuple synchronized grammars

Sébastien Limet (1), Pierre Réty (1)
(1) Laboratoire d'Informatique Fondamentale d'Orléans
Download article
Open on HAL
Imported on
March 26, 2015
Published on
January 1, 1997
Last modified on
March 31, 2025
Volume 1
vol. 1
DOI
10.46298/dmtcs.240
License
https://about.hal.science/hal-authorisation-v1
Indicators
680
Views
779
Downloads

E-unification by means of tree tuple synchronized grammars

Sébastien Limet (1), Pierre Réty (1)
(1) Laboratoire d'Informatique Fondamentale d'Orléans
Abstract
The goal of this paper is both to give an E-unification procedure that always terminates, and to decide unifiability. For this, we assume that the equational theory is specified by a confluent and constructor-based rewrite system, and that four additional restrictions are satisfied. We give a procedure that represents the (possibly infinite) set of solutions thanks to a tree tuple synchronized grammar, and that can decide upon unifiability thanks to an emptiness test. Moreover, we show that if only three of the four additional restrictions are satisfied then unifiability is undecidable.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • E-unification
  • narrowing
  • tree languages
  • decidability
Cited by

Source: OpenCitations

  • E-unification by means of tree tuple synchronized grammars

    Lecture notes in computer science

    Authors : Sébastien Limet, Pierre Réty

    Journal reference : Volume , 1997, pp. 429-440

    DOI : 10.1007/bfb0030616
  • Basic Syntactic Mutation

    Lecture notes in computer science

    Authors : Christopher Lynch ORCID, Barbara Morawska ORCID

    Journal reference : Volume , 2002, pp. 471-485

    DOI : 10.1007/3-540-45620-1_37
  • Manipulating Tree Tuple Languages by Transforming Logic Programs1 1Extended abstract; see http://www.logic.at/css/ftp03.pdf for the proofs.

    Electronic Notes in Theoretical Computer Science

    Authors : Sébastien Limet, Gernot Salzer ORCID

    Journal reference : Volume 86, 2003, pp. 76-90

    DOI : 10.1016/s1571-0661(04)80654-6
  • Solving First Order Formulae of Pseudo-Regular Theory

    Lecture notes in computer science

    Authors : Sébastien Limet, Pierre Pillot

    Journal reference : Volume , 2005, pp. 110-124

    DOI : 10.1007/11560647_7
  • Tree Tuple Languages from the Logic Programming Point of View

    Journal of Automated Reasoning

    Authors : Sébastien Limet, Gernot Salzer ORCID

    Journal reference : Volume 37, 2007, pp. 323-349

    DOI : 10.1007/s10817-006-9064-8
  • A Unified Framework to Compute over Tree Synchronized Grammars and Primal Grammars

    Discrete Mathematics & Theoretical Computer Science

    Authors : Frédéric Saubion ORCID, Igor Stéphan ORCID

    Journal reference : Volume Vol. 5, 2002, pp.

    DOI : 10.46298/dmtcs.300
  • On Implementation of Tree Synchronized Languages

    Lecture notes in computer science

    Authors : Frédéric Saubion ORCID, Igor Stéphan ORCID

    Journal reference : Volume , 1999, pp. 382-396

    DOI : 10.1007/3-540-48685-2_30
  • Proving Properties of Term Rewrite Systems via Logic Programs

    Lecture notes in computer science

    Authors : Sébastien Limet, Gernot Salzer ORCID

    Journal reference : Volume , 2004, pp. 170-184

    DOI : 10.1007/978-3-540-25979-4_12
Preview
Loading PDF preview...