Refined Notions of QBF Equivalences

Peter Pfeiffer; Daniel Große; Martina Seidl

doi:10.1007/978-3-032-04590-4_11

Refined Notions of QBF Equivalences

Peter Pfeiffer^*
, Daniel Große
, Martina Seidl

^*Korrespondierende/r Autor/-in für diese Arbeit

Publikation: Beitrag in Buch/Bericht/Konferenzband › Konferenzbeitrag › Begutachtung

Abstract

Usually, two quantified Boolean formulas (QBFs) are said to be equivalent if they have the same truth value for every assignment to the free variables. This notion of equivalence is very coarse-grained in the sense that it considers only assignments to the free variables, but it does not take the models or counter-models of the two QBFs into account. In this paper, we investigate refined notions of equivalences on the solution level to obtain a more fine-grained comparison of two formulas. We show that the problem of checking solution equivalence is PSPACE complete.

Originalsprache	Englisch
Titel	Logics in Artificial Intelligence - 19th European Conference, JELIA 2025, Proceedings
Untertitel	19th European Conference, JELIA 2025, Kutaisi, Georgia, September 1–4, 2025, Proceedings, Part II
Herausgeber*innen	Giovanni Casini, Besik Dundua, Temur Kutsia
Verlag	Springer, Cham
Seiten	159–165
Seitenumfang	7
Auflage	1
ISBN (elektronisch)	978-3-032-04590-4
ISBN (Print)	978-3-032-04589-8
DOIs	https://doi.org/10.1007/978-3-032-04590-4_11
Publikationsstatus	Veröffentlicht - 2026
Veranstaltung	19th edition of the European Conference on Logics in Artificial Intelligence - Kutaisi International University KIU, Kutaisi, Georgien Dauer: 01 Sep. 2025 → 04 Sep. 2025 Konferenznummer: 2025 https://viam.science.tsu.ge/jelia2025/

Publikationsreihe

Name	Lecture Notes in Computer Science
Band	16094 LNAI
ISSN (Print)	0302-9743
ISSN (elektronisch)	1611-3349

Konferenz

Konferenz	19th edition of the European Conference on Logics in Artificial Intelligence
Kurztitel	JELIA
Land/Gebiet	Georgien
Ort	Kutaisi
Zeitraum	01.09.2025 → 04.09.2025
Internetadresse	https://viam.science.tsu.ge/jelia2025/

Wissenschaftszweige

102031 Theoretische Informatik
603109 Logik
102011 Formale Sprachen
102022 Softwareentwicklung
102001 Artificial Intelligence
101013 Mathematische Logik
102030 Semantische Technologien
102 Informatik
202017 Embedded Systems
101015 Operations Research
102005 Computer Aided Design (CAD)
202041 Technische Informatik
202005 Computer Architektur

JKU-Schwerpunkte

Digital Transformation

Zugriff auf Dokument

10.1007/978-3-032-04590-4_11

Andere Dateien und Links

Verknüpfung zur Publikation in Scopus

Dieses zitieren

Pfeiffer, P., Große, D., & Seidl, M. (2026). Refined Notions of QBF Equivalences. in G. Casini, B. Dundua, & T. Kutsia (Hrsg.), Logics in Artificial Intelligence - 19th European Conference, JELIA 2025, Proceedings: 19th European Conference, JELIA 2025, Kutaisi, Georgia, September 1–4, 2025, Proceedings, Part II (1 Aufl., S. 159–165). (Lecture Notes in Computer Science; Band 16094 LNAI). Springer, Cham. https://doi.org/10.1007/978-3-032-04590-4_11

Pfeiffer, Peter ; Große, Daniel ; Seidl, Martina. / Refined Notions of QBF Equivalences. Logics in Artificial Intelligence - 19th European Conference, JELIA 2025, Proceedings: 19th European Conference, JELIA 2025, Kutaisi, Georgia, September 1–4, 2025, Proceedings, Part II. Hrsg. / Giovanni Casini ; Besik Dundua ; Temur Kutsia. 1. Aufl. Springer, Cham, 2026. S. 159–165 (Lecture Notes in Computer Science).

@inproceedings{de7b7e9517a84bff81442bbd01fe3b9f,

title = "Refined Notions of QBF Equivalences",

abstract = "Usually, two quantified Boolean formulas (QBFs) are said to be equivalent if they have the same truth value for every assignment to the free variables. This notion of equivalence is very coarse-grained in the sense that it considers only assignments to the free variables, but it does not take the models or counter-models of the two QBFs into account. In this paper, we investigate refined notions of equivalences on the solution level to obtain a more fine-grained comparison of two formulas. We show that the problem of checking solution equivalence is PSPACE complete.",

author = "Peter Pfeiffer and Daniel Gro{\ss}e and Martina Seidl",

year = "2026",

doi = "10.1007/978-3-032-04590-4\_11",

language = "English",

isbn = "978-3-032-04589-8",

series = "Lecture Notes in Computer Science",

publisher = "Springer, Cham",

pages = "159{\textendash}165",

editor = "Giovanni Casini and Besik Dundua and Temur Kutsia",

booktitle = "Logics in Artificial Intelligence - 19th European Conference, JELIA 2025, Proceedings",

edition = "1",

note = "19th edition of the European Conference on Logics in Artificial Intelligence, JELIA ; Conference date: 01-09-2025 Through 04-09-2025",

url = "https://viam.science.tsu.ge/jelia2025/",

}

Pfeiffer, P , Große, D & Seidl, M 2026, Refined Notions of QBF Equivalences. in G Casini, B Dundua & T Kutsia (Hrsg.), Logics in Artificial Intelligence - 19th European Conference, JELIA 2025, Proceedings: 19th European Conference, JELIA 2025, Kutaisi, Georgia, September 1–4, 2025, Proceedings, Part II. 1 Aufl., Lecture Notes in Computer Science, Bd. 16094 LNAI, Springer, Cham, S. 159–165, 19th edition of the European Conference on Logics in Artificial Intelligence, Kutaisi, Georgien, 01.09.2025. https://doi.org/10.1007/978-3-032-04590-4_11

Refined Notions of QBF Equivalences. / Pfeiffer, Peter ; Große, Daniel ; Seidl, Martina.
Logics in Artificial Intelligence - 19th European Conference, JELIA 2025, Proceedings: 19th European Conference, JELIA 2025, Kutaisi, Georgia, September 1–4, 2025, Proceedings, Part II. Hrsg. / Giovanni Casini; Besik Dundua; Temur Kutsia. 1. Aufl. Springer, Cham, 2026. S. 159–165 (Lecture Notes in Computer Science; Band 16094 LNAI).

Publikation: Beitrag in Buch/Bericht/Konferenzband › Konferenzbeitrag › Begutachtung

TY - GEN

T1 - Refined Notions of QBF Equivalences

AU - Pfeiffer, Peter

AU - Große, Daniel

AU - Seidl, Martina

N1 - Conference code: 2025

PY - 2026

Y1 - 2026

N2 - Usually, two quantified Boolean formulas (QBFs) are said to be equivalent if they have the same truth value for every assignment to the free variables. This notion of equivalence is very coarse-grained in the sense that it considers only assignments to the free variables, but it does not take the models or counter-models of the two QBFs into account. In this paper, we investigate refined notions of equivalences on the solution level to obtain a more fine-grained comparison of two formulas. We show that the problem of checking solution equivalence is PSPACE complete.

AB - Usually, two quantified Boolean formulas (QBFs) are said to be equivalent if they have the same truth value for every assignment to the free variables. This notion of equivalence is very coarse-grained in the sense that it considers only assignments to the free variables, but it does not take the models or counter-models of the two QBFs into account. In this paper, we investigate refined notions of equivalences on the solution level to obtain a more fine-grained comparison of two formulas. We show that the problem of checking solution equivalence is PSPACE complete.

UR - https://www.scopus.com/pages/publications/105016190487

U2 - 10.1007/978-3-032-04590-4_11

DO - 10.1007/978-3-032-04590-4_11

M3 - Conference proceedings

SN - 978-3-032-04589-8

T3 - Lecture Notes in Computer Science

SP - 159

EP - 165

BT - Logics in Artificial Intelligence - 19th European Conference, JELIA 2025, Proceedings

A2 - Casini, Giovanni

A2 - Dundua, Besik

A2 - Kutsia, Temur

PB - Springer, Cham

T2 - 19th edition of the European Conference on Logics in Artificial Intelligence

Y2 - 1 September 2025 through 4 September 2025

ER -

Pfeiffer P , Große D , Seidl M. Refined Notions of QBF Equivalences. in Casini G, Dundua B, Kutsia T, Hrsg., Logics in Artificial Intelligence - 19th European Conference, JELIA 2025, Proceedings: 19th European Conference, JELIA 2025, Kutaisi, Georgia, September 1–4, 2025, Proceedings, Part II. 1 Aufl. Springer, Cham. 2026. S. 159–165. (Lecture Notes in Computer Science). Epub 2025 Aug. 29. doi: 10.1007/978-3-032-04590-4_11