License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.RTA.2012.38
URN: urn:nbn:de:0030-drops-34838
Go to the corresponding LIPIcs Volume Portal

Al-Hassani, Osama ; Mahesar, Quratul-ain ; Sacerdoti Coen, Claudio ; Sorge, Volker

A Term Rewriting System for Kuratowski's Closure-Complement Problem

6.pdf (0.6 MB)


We present a term rewriting system to solve a class of open problems that are generalisations of Kuratowski's closure-complement theorem. The problems are concerned with finding the number of distinct sets that can be obtained by applying combinations of axiomatically defined set operators. While the original problem considers only closure and complement of a topological space as operators, it can be generalised by adding operators and varying axiomatisation. We model these axioms as rewrite rules and construct a rewriting system that allows us to close some so far open variants of Kuratowski's problem by analysing several million inference steps on a typical personal computer.

BibTeX - Entry

  author =	{Osama Al-Hassani and Quratul-ain Mahesar and Claudio Sacerdoti Coen and Volker Sorge},
  title =	{{A Term Rewriting System for Kuratowski's Closure-Complement Problem}},
  booktitle =	{23rd International Conference on Rewriting Techniques and Applications (RTA'12) },
  pages =	{38--52},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-38-5},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{15},
  editor =	{Ashish Tiwari},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-34838},
  doi =		{10.4230/LIPIcs.RTA.2012.38},
  annote =	{Keywords: Kuratowski's closure-complement problem, Rewriting system}

Keywords: Kuratowski's closure-complement problem, Rewriting system
Collection: 23rd International Conference on Rewriting Techniques and Applications (RTA'12)
Issue Date: 2012
Date of publication: 29.05.2012

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI