• DocumentCode
    2894084
  • Title

    Decidable problems in shallow equational theories

  • Author

    Comon, Hubert ; Haberstrau, Marianne ; Jouannaud, Jean-Pierre

  • Author_Institution
    Univ. de Paris Sud, Orsay, France
  • fYear
    1992
  • fDate
    22-25 Jun 1992
  • Firstpage
    255
  • Lastpage
    265
  • Abstract
    Results for syntactic theories are generalized to shallow theories. The main technique used is the computation by ordered completion techniques of conservative extensions of the starting shallow presentation which are, respectively, ground convergent, syntactic, and cycle-syntactic. In all cases, the property that variables occur at depth at most one appears to be crucial. shallow theories thus emerge as a fundamental nontrivial, union-closed subclass of equational theories for which all important questions are decidable
  • Keywords
    decidability; cycle-syntactic; decidability; equational theories; ground convergent; ordered completion; shallow equational theories; syntactic; syntactic theories; Algebra; Equations;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Logic in Computer Science, 1992. LICS '92., Proceedings of the Seventh Annual IEEE Symposium on
  • Conference_Location
    Santa Cruz, CA
  • Print_ISBN
    0-8186-2735-2
  • Type

    conf

  • DOI
    10.1109/LICS.1992.185538
  • Filename
    185538