Abschlussarbeit

Bachelorarbeit: "A Skeptical Notion of Variable Forgetting"

Ansprechperson:
Dr. Kai Sauerwald
Status:
Themenangebot

Beschreibung:

Propositional logic is one of the fundamental logics of computer science and beyond. Its application ranges from acting as a canonic example in theoretical computer science (where it gives rise to the famous SAT problem) over application in modelling to being the foundation for circuits.
One problem when using propositional logic is that the complexity of propositional logic depends on the number of atoms used in the logic. To reduce the number of atoms in applications, one can focus on the relevant atoms case by case. Technically, this can be done by variable forgetting (also called variable elimination), an operation defined syntactically. Given a formula 'A' defined over a signature P, the variable forgetting of an atom 'a' is the formula obtained by replacing all occurrences of 'a' in 'A' by a tautology disjointed with replacing all occurrences of 'a' in 'A' by a falsum. One can easily observe that variable forgetting is very drastic, e.g., forgetting an atom results in a tautological formula, even in cases where one might not excepted this.
This thesis investigates a more cautious notion of variable forgetting (which we call here "sceptical variable forgetting"), which is given semantically and defined by the artificial intelligence group. This aim is to explore the possibility of a syntactic characterization of sceptical variable forgetting. Furthermore, depending on the preferences of the student, a demonstrator system of sceptical variable forgetting can be implemented, canonical examples can be identified, and/or formal properties of such a forgetting operation can be explored.
Literature:
Lang, Liberatore and Marquis: Propositional Independence: Formula-Variable Independence and Forgetting. J. Artif. Intell. Res., 2003, 18, 391-443
Lin and Reiter: Forget It!. Proceedings of the AAAI Fall Symposium on Relevance, AAAI Press, Menlo Park, CA, 1994, 154-159
Zhang and Zhou: Knowledge forgetting: Properties and applications. Artificial Intelligence, 2009, 173, 1525 - 1537
10.05.2024