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

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference proceedings › peer-review

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.

Original language	English
Title of host publication	Logics in Artificial Intelligence - 19th European Conference, JELIA 2025, Proceedings
Subtitle of host publication	19th European Conference, JELIA 2025, Kutaisi, Georgia, September 1–4, 2025, Proceedings, Part II
Editors	Giovanni Casini, Besik Dundua, Temur Kutsia
Publisher	Springer, Cham
Pages	159–165
Number of pages	7
Edition	1
ISBN (Electronic)	978-3-032-04590-4
ISBN (Print)	978-3-032-04589-8
DOIs	https://doi.org/10.1007/978-3-032-04590-4_11
Publication status	Published - 2026
Event	19th edition of the European Conference on Logics in Artificial Intelligence - Kutaisi International University KIU, Kutaisi, Georgia Duration: 01 Sept 2025 → 04 Sept 2025 Conference number: 2025 https://viam.science.tsu.ge/jelia2025/

Publication series

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

Conference

Conference	19th edition of the European Conference on Logics in Artificial Intelligence
Abbreviated title	JELIA
Country/Territory	Georgia
City	Kutaisi
Period	01.09.2025 → 04.09.2025
Internet address	https://viam.science.tsu.ge/jelia2025/

Fields of science

102031 Theoretical computer science
603109 Logic
102011 Formal languages
102022 Software development
102001 Artificial intelligence
101013 Mathematical logic
102030 Semantic technologies
102 Computer Sciences
202017 Embedded systems
101015 Operations research
102005 Computer aided design (CAD)
202041 Computer engineering
202005 Computer architecture

JKU Focus areas

Digital Transformation

Access to Document

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

Cite this

Pfeiffer, P., Große, D., & Seidl, M. (2026). Refined Notions of QBF Equivalences. In G. Casini, B. Dundua, & T. Kutsia (Eds.), 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 ed., pp. 159–165). (Lecture Notes in Computer Science; Vol. 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. editor / Giovanni Casini ; Besik Dundua ; Temur Kutsia. 1. ed. Springer, Cham, 2026. pp. 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 (eds), 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 edn, Lecture Notes in Computer Science, vol. 16094 LNAI, Springer, Cham, pp. 159–165, 19th edition of the European Conference on Logics in Artificial Intelligence, Kutaisi, Georgia, 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. ed. / Giovanni Casini; Besik Dundua; Temur Kutsia. 1. ed. Springer, Cham, 2026. p. 159–165 (Lecture Notes in Computer Science; Vol. 16094 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceedings › peer-review

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, editors, 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 ed. Springer, Cham. 2026. p. 159–165. (Lecture Notes in Computer Science). Epub 2025 Aug 29. doi: 10.1007/978-3-032-04590-4_11

Refined Notions of QBF Equivalences

Abstract

Publication series

Conference

Fields of science

JKU Focus areas

Access to Document

Other files and links

Cite this