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

Direct link
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.
Uppsala theses in computing science, ISSN 0283-359X ; 29
National Category
Computer Science
Research subject
Computing Science
URN: urn:nbn:se:uu:diva-1197ISBN: 91-506-1217-4OAI: oai:DiVA.org:uu-1197DiVA: diva2:160751
Public defence
1997-06-06, Room 1311, Polacksbacken, Uppsala University, Uppsala, 10:15 (English)
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
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 719 hits
ReferencesLink to record
Permanent link

Direct link