uu.seUppsala universitets publikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet 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 (engelsk)Doktoravhandling, monografi (Annet vitenskapelig)
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.

sted, utgiver, år, opplag, sider
Uppsala universitet, 1997. , s. 122
Serie
Uppsala theses in computing science, ISSN 0283-359X ; 29
HSV kategori
Forskningsprogram
Datalogi
Identifikatorer
URN: urn:nbn:se:uu:diva-1197ISBN: 91-506-1217-4 (tryckt)OAI: oai:DiVA.org:uu-1197DiVA, id: diva2:160751
Disputas
1997-06-06, Room 1311, Polacksbacken, Uppsala University, Uppsala, 10:15 (engelsk)
Veileder
Tilgjengelig fra: 1997-05-16 Laget: 1997-05-16 Sist oppdatert: 2018-01-13bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric

isbn
urn-nbn
Totalt: 1530 treff
RefereraExporteraLink to record
Permanent link

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