uu.seUppsala universitets publikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
On Simultaneous Rigid E-Unification
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för ADB och datalogi.
1997 (Engelska)Doktorsavhandling, monografi (Övrigt vetenskapligt)
Abstract [en]

Automated theorem proving methods in classical logic with equality that are based on the Herbrand theorem, reduce to a problem called Simultaneous Rigid E-Unification, or SREU for short. Recent developments show that SREU has also close connections with intuitionistic logic with equality, second-order unification, some combinatorial problems and finite tree automata.

We show new decidability results of various cases of SREU. In particular, we improve upon the undecidability result of SREU by showing its undecidability in a very restricted case, in fact the minimal known case. We prove the decidability of some cases of SREU under certain restrictions regarding the number of variables and other syntactical criteria. To prove the (computational) complexity of some cases, we reduce them to certain decision problems of finite tree automata. The complexity of the latter problems is studied first. In connection with that, we present a survey of closely related problems and give a comparison with the corresponding results in classical automata theory.

These results are applied in the context of intuitionistic logic with equality, to obtain a complete classification of its prenex fragment in terms of the quantifier prefix: the ∃∃-fragment is shown undecidable and the ∀*∃∀*-fragment is shown decidable. These results have further implications for proof search in intuitionistic logic with equality.

We also improve upon a number of other recent undecidability results that are related to the so-called Herbrand Skeleton problem and are of fundamental importance in automated theorem proving in in classical logic with equality. In that context we also prove, as our main tool, a logical theorem that we believe is of independent interest.

Ort, förlag, år, upplaga, sidor
Uppsala universitet, 1997. , s. 122
Serie
Uppsala theses in computing science, ISSN 0283-359X ; 29
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
Datalogi
Identifikatorer
URN: urn:nbn:se:uu:diva-1197ISBN: 91-506-1217-4 (tryckt)OAI: oai:DiVA.org:uu-1197DiVA, id: diva2:160751
Disputation
1997-06-06, Room 1311, Polacksbacken, Uppsala University, Uppsala, 10:15 (Engelska)
Handledare
Tillgänglig från: 1997-05-16 Skapad: 1997-05-16 Senast uppdaterad: 2018-01-13Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Av organisationen
Institutionen för ADB och datalogi
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetricpoäng

isbn
urn-nbn
Totalt: 1532 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf