uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On Simultaneous Rigid E-Unification
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Computing Science Department.
1997 (English)Doctoral thesis, monograph (Other academic)
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.

Place, publisher, year, edition, pages
Uppsala universitet, 1997. , 122 p.
Series
Uppsala theses in computing science, ISSN 0283-359X ; 29
National Category
Computer Science
Research subject
Computing Science
Identifiers
URN: urn:nbn:se:uu:diva-1197ISBN: 91-506-1217-4 (print)OAI: oai:DiVA.org:uu-1197DiVA: diva2:160751
Public defence
1997-06-06, Room 1311, Polacksbacken, Uppsala University, Uppsala, 10:15 (English)
Supervisors
Available from: 1997-05-16 Created: 1997-05-16 Last updated: 2015-01-29Bibliographically approved

Open Access in DiVA

No full text

By organisation
Computing Science Department
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 1326 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf