Research map / Learning theory and algorithms / Combinatorial and search optimization
An Alternative Theory of Stable Revision for Nondeterministic Approximation Fixpoint Theory and the Relationships
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes approximator sets, a theory that defines nondeterministic stable revision by lifting deterministic AFT stable revision to sets of approximators, applies it to partial stable models of disjunctive logic programs, and relates it to nondeterministic AFT.
Problem
Nondeterministic approximation fixpoint theory (AFT) departs from deterministic AFT with its own fixpoints, exactness, monotonicity and orderings; it is unclear whether nondeterministic stable revision can be defined directly with deterministic AFT.
Approach
Represent a nondeterministic operator as a set (approximator set) of deterministic approximators, define gamma-stable fixpoints by truth-minimality over the stable revisions of all members, and relate the result to nondeterministic AFT's n-stable fixpoints via induced operators and alpha-stable fixpoints.
Key results
- Shows that gamma-stable fixpoints of the approximator set induced by a disjunctive logic program coincide with its (partial) stable models (Theorem 4.1).
- Proves that alpha-stable fixpoints of an approximator set are exactly the n-stable fixpoints of the induced nondeterministic approximator (Theorem 5.2 and Corollary 5.3, under stable-consistency).
- Gives examples where a DLP has no gamma-stable fixpoint (Example 6) and where gamma-stable fixpoints are not alpha-stable (Example 8).
Surprising findings
- A gamma-stable fixpoint may fail to exist for some disjunctive logic programs, e.g., one with no partial stable model.
- Not every nondeterministic approximator has an inducing approximator set; some are excluded by ordering or monotonicity constraints.
Limitations
- Approximator sets do not capture all partial stable models of DLPs (alpha-stable fixpoints are strictly narrower).
- Inconsistent pairs are needed by some AFT variants (e.g., Bi et al. relaxed exactness) and cannot be adapted to nondeterministic approximators.
- Results are restricted to simple disjunctive logic programs; the two-valued Shen-Eiter comparison covers only two-valued semantics.
Experimental setup
Baselines: Nondeterministic AFT (Heyninck et al. 2024) Possible model semantics (Sakama 1990) Determining inference semantics (Shen and Eiter 2019)
Builds on: Approximation fixpoint theory (Denecker, Marek, Truszczynski 2000) Nondeterministic AFT (Heyninck et al. 2024) Partial stable semantics (Przymusinski 1991)
Closest papers by meaning
- An Algebraic Notion of Conditional Independence, and Its Application to Knowledge Representation (AAAI 2025 · similarity 0.87)
- Minimal Change in Modal Logic S5 (AAAI 2025 · similarity 0.87)
- A Unified View on Forgetting and Strong Equivalence Notions in Answer Set Programming (AAAI 2024 · similarity 0.84)
- Stable Model Semantics for Description Logic Terminologies (AAAI 2024 · similarity 0.84)
- Dung’s Argumentation Framework: Unveiling the Expressive Power with Inconsistent Databases (AAAI 2025 · similarity 0.84)
- A Variable Occurrence-Centric Framework for Inconsistency Handling (AAAI 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.