An Undecidable Fragment of the Theory of Set Constraints

Charatonik, Witold

Local TagsRelease HistoryDetailsSummary

An Undecidable Fragment of the Theory of Set Constraints

Charatonik, W. (1998). An Undecidable Fragment of the Theory of Set Constraints. Information Processing Letters, 68, 147-151.

Item is Released

show all hide all

Basic

show hide

Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3815-8 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3816-6

Genre: Journal Article

Files

show Files

Locators

show

Creators

show

hide

Creators:
Charatonik, Witold¹, Author

Affiliations:
1Programming Logics, MPI for Informatics, Max Planck Society, ou_40045

Content

show

hide

Free keywords: -

Abstract: Set constraints are inclusions between expressions denoting sets of trees. In atomic set constraints, the syntax of set expressions is restricted not to contain any Boolean set operators. Using a reduction from the Hilbert's Tenth Problem we prove the undecidability of the $\exists^*\forall^*$-fragment of the first-order theory of atomic set constraints. This improves recent results by Seynhaeve et.\ al.

Details

show

hide

Language(s): eng - English

Dates: Modified: 2010-03-12Date issued: 1998

Publication Status: Issued

Pages: -

Publishing info: -

Table of Contents: -

Rev. Type: Peer

Identifiers: eDoc: 519673
Other: Local-ID: C1256104005ECAFC-FD6026676FDD56B0412566F800633870-Charatonik-IPL98

Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show

hide

Title: Information Processing Letters

Source Genre: Journal

Creator(s):

Affiliations:

Publ. Info: -

Pages: - Volume / Issue: 68 Sequence Number: - Start / End Page: 147 - 151 Identifier: ISSN: 0020-0190