PaperlayerView exact revision on arXiv

Source-linked AI summary

Extensions of Simple Conceptual Graphs: the Complexity of Rules and Constraints

J. F. Baget, M. L. Mugnier

arXiv:1106.1800v1cs.AI

TL;DR

The graph-theoretic foundations of this reasoning area have received less investigation. The paper extends simple graphs with rules and constraints while retaining projection, then shows that rules bring undecidability but restricted cases can be decidable or fall in the polynomial hierarchy.

  • Problem

    The graph-theoretic foundations of this area have been less investigated than its other aspects.

    Source: §1 · p. 1

  • Method

    The paper studies rule and constraint extensions of simple graphs using projection, a graph-homomorphism operation.

    Source: §1 · p. 2, §2.1 · p. 4, §7.3 · p. 34

  • Results

    With rules, associated decision problems are undecidable, while finite expansion sets ensure computations stop and range-restricted rules place their complexity in the polynomial hierarchy.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Deduction in the simple-graph model is NP-complete.

    Source: §2.3 · p. 7

    The paper identifies range-restricted constraints as trickier to study, with consistency singled out in that discussion.

    Source: §7.3 · p. 34

Abstract

from arXiv · show

Simple conceptual graphs are considered as the kernel of most knowledge representation formalisms built upon Sowa's model. Reasoning in this model can be expressed by a graph homomorphism called projection, whose semantics is usually given in terms of positive, conjunctive, existential FOL. We present here a family of extensions of this model, based on rules and constraints, keeping graph homomorphism as the basic operation. We focus on the formal definitions of the different models obtained, including their operational semantics and relationships with FOL, and we analyze the decidability and complexity of the associated problems (consistency and deduction). As soon as rules are involved in reasonings, these problems are not decidable, but we exhibit a condition under which they fall in the polynomial hierarchy. These results extend and complete the ones already published by the authors. Moreover we systematically study the complexity of some particular cases obtained by restricting the form of constraints and/or rules.

1. In tro du tion

The paper presents a unifying framework for simple-graph extensions that combine rules and constraints while retaining projection-based reasoning. It defines the resulting models and studies the decidability and complexity of consistency and deduction.

1. In tro du ction

  • The framework combines rules and constraints in different ways while retaining projection as its basic operation.The paper notes that this combination had not previously been studied in reasoning.Source: §1 · p. 2
  • The paper formalizes the resulting models, their operational semantics and FOL relationships, and their consistency and deduction problems.These results extend and complete earlier work by the authors (Baget & Mugnier, 2001).Source: §1 · p. 2
  • The authors give a detailed complexity analysis for range-restricted rules and examine particular cases defined by restricting rules or constraints.The range-restricted-rule analysis is presented as a first detailed treatment of its complexity.Source: §1 · p. 2
  • With rules, the associated decision problems are undecidable; finite expansion sets ensure computations stop, and range-restricted rules place these problems in the polynomial hierarchy.The paper also studies complexity for particular restrictions on rules and constraints.Source: §1 · p. 2
  • Consistency for simple graphs with constraints is equivalent to deciding consistency for a mixed constraint-satisfaction problem (MIXED-SAT).The paper points to algorithmic connections with constraint satisfaction problems.Source: §1 · p. 2

2. Basi Notions: the S G Mo del

This section presents simple conceptual graphs as a knowledge-representation model and relates projection-based reasoning to existential conjunctive positive FOL through projection-preserving translations. It also examines the complexity of SG deduction and graph projection, and characterizes redundancy using projection equivalence, including its complexity and canonical forms.

2.1 De nitions and Notations

  • Simple graphs are finite bipartite labeled multigraphs, and projection is a graph homomorphism that preserves edges and label specialization.A query projects into a fact graph when its nodes can be mapped while preserving these structures; such projections define query answers.Source: §2.1 · pp. 4–5

2.2 Relationships with F OL

  • Each support and simple graph has a FOL translation, and projection is sound and complete for this semantics when graphs are in normal form.Normal form merges concept nodes with the same individual marker; it always exists and can be computed in linear time with a naive algorithm.Source: §2.2 · p. 5
  • A query Q projects into the normal form of G exactly when the support and G entail the FOL translation of Q.Graphs with the same logical translation can be incomparable by projection if they are not in normal form.Source: §2.2 · p. 5
  • A bijection maps FOL formulas to normal SGs over a flat support, with φ entailing ψ exactly when ψ's graph projects into φ's graph.Source: §2.2 · p. 6
  • Conversely, normal SGs on a support inject into FOL formulas, with projection from H to G equivalent to entailment from G's translation to H's.Source: §2.2 · p. 6

2.3 The Dedu tion Problem: Computational Complexit y

  • The authors give a 3-SAT reduction proof of projection's NP-completeness, noting that it is more involved than earlier proofs but underpins later reductions.Source: §2.3 · p. 7
  • SG deduction is NP-complete when type checking in the support is in NP, and remains NP-complete when type checking is O(1) (Chein & Mugnier, 1992).The theorem relates membership in NP for deduction to type-checking complexity; its hardness result holds even with constant-time type checking.Source: §2.3 · p. 7
  • A polynomial construction maps a 3-SAT formula F to graphs Q(F) and G(F), with F satisfiable iff Q(F) projects into G(F).Q(F) represents whether there is a variable valuation making every clause true.Source: §2.3 · p. 8

2.4 A Note on Redundan y

  • Projection-induced subsumption is reflexive and transitive but not antisymmetric; mutually projecting graphs are equivalent, and a graph equivalent to a strict subgraph is redundant.Source: §2.4 · p. 8
  • Redundancy checking is NP-complete, and every projection-equivalence class has a unique irredundant graph up to isomorphism (Chein & Mugnier, 1992).Source: §2.4 · p. 8

3. The S G F amily: Extensions of Simple Con eptual Graphs

The section presents the SG family as an extension of simple conceptual graphs that preserves graph projection as a core reasoning operation, and introduces how facts, rules, and deduction work. It formalizes knowledge bases with inference and evolution rules and constraints, identifies six models, and distinguishes two forms of undecidability.

3.1 Knowledge Representation and Reasonings with Graphs

  • A document-retrieval experiment found the system feasible in computing time and more relevant than the existing RAMEAU-based system, mainly through semantic relations rather than keywords alone.Indexers learned the tool quickly, and a senior librarian judged their resulting indexations high quality.Source: §3.1 · p. 9
  • For knowledge engineering, the proposed approach supports simulation during model design, letting experts follow reasoning step by step before costly late-stage validation and changes.The project chose simple graphs and readable extensions rather than general conceptual graphs equivalent to FOL.Source: §3.1 · p. 9
  • The authors aim to extend simple conceptual graphs while keeping objects and reasoning readable and the extensions preferably logically founded.They present the SG family as a first step toward that aim.Source: §3.1 · p. 10

3.2 An Overview of the SG Family

  • In the basic SG model, a knowledge base contains simple graphs representing facts, and deduction asks whether the query graph projects into those facts.The family’s more complex rules and constraints are also based on simple graphs, and operations on them use projection.Source: §3.2 · p. 10
  • A rule adds its conclusion when its hypothesis projects into a graph; distinct projections can yield different applications and new information.Rules encode the hypothesis and conclusion as differently colored subgraphs.Source: §3.2 · pp. 10–11
  • Rule-based deduction asks whether some sequence of applications makes the query project into an enriched graph; applying rules until no new information appears is not always finite.The illustrated example terminates, but the passage cautions that this does not hold in general.Source: §3.2 · p. 11

3.2 An Ov erview of the S G F amily

  • Positive constraints require each condition projection to extend to the whole graph, whereas negative constraints forbid such an extension.Constraints are represented as bi-colored simple graphs, with one color marking the condition and the other the required or forbidden part.Source: §3.2 · p. 11
  • Inference rules make implicit knowledge explicit, and consistency requires constraint violations to be repairable through rule applications before deduction is allowed.When the world description can be fully made explicit as a finite graph with respect to the rules, consistency can be checked on that graph.Source: §3.2 · pp. 12–13
  • Evolution rules represent transitions between worlds, and deduction asks whether a query holds in a world reachable along a path of consistent worlds.Facts describe the initial world, constraints define consistency for each world, and evolution-rule applications generate successor worlds.Source: §3.2 · p. 13

3.3 The S G F amily

  • A knowledge base is represented as facts G, inference rules R, evolution rules E, and constraints C, with positive and negative constraints distinguished.The formalism defines the deduction problem as deciding whether a goal can be deduced from the knowledge base.Source: §3.3 · pp. 13–14
  • The family defines six models—SG, SR, SGC, SRC, SEC, and SREC—by varying which rule and constraint sets are present.Without constraints, inference and evolution rules behave alike and can be treated as interchangeable.Source: §3.3 · p. 14
  • Figure 9 presents the models’ hierarchy and highlights decidability and complexity properties of their associated deduction problems.The supplied passage does not state the individual results shown in the figure.Source: §3.3 · p. 14
  • The text distinguishes problems with finite answers for all positive but not all negative instances from truly undecidable problems with no finite procedure for either.Source: §3.3 · p. 14
  • Figure 9 presents the S G family models and the complexity of their associated deduction problem.Source: Figure 9 · p. 14

4. SGs and Rules: the S R Mo del

The SR model represents rules as simple graphs and uses projection-based rule application to derive graphs and answer deduction queries. Its logical semantics is characterized in FOL, while deduction is semi-decidable but not decidable, including for rules of the form “if A then B.”

4. SGs and Rules: the S R Mo del

  • Simple graph rules encode “if A then B” knowledge using a colored graph, with hypothesis and conclusion represented as separate parts.The model retains graph homomorphism, specifically projection, as the basic operation for rule application.Source: §4 · p. 14, §4.1 · p. 15

4.1 De nitions and Notations

  • A rule is applied when its hypothesis projects into a graph; application adds a disjoint copy of the rule conclusion.A derivation is a sequence of rule applications, and a query is deduced when it projects into a graph reached by such a sequence.Source: §4.1 · p. 15

4.2 Logi al Seman ti s

  • SR deduction is equivalent to FOL entailment for the translated knowledge base and query, assuming graphs are normalized after each rule application.Rule conclusions introduce existentially quantified variables in the logical translation.Source: §4.2 · p. 15

4.3 A Semi-de idable Problem

  • SR-deduction is semi-decidable: breadth-first search finds a derivation when one exists, and a reduction from the semi-Thue word problem establishes undecidability.The reduction also shows semi-decidability persists for rules of the form “if A then B.”Source: §4.3 · p. 16

5. SGs and Constrain ts: the S G C Mo del

The section studies consistency and deduction for simple conceptual graphs with constraints, relating constraint satisfaction and positive constraints to graph equivalence, first-order logic, and rule application. It also characterizes complexity for SGC, including the distinction between positive and negative constraints.

5.1 De nitions and Some Immediate Prop erties

  • A graph violates a constraint when a projection of its trigger cannot extend to a projection of the whole constraint; positive constraints test the irredundant graph form.For negative constraints, the test uses the graph itself.Source: §5.1 · p. 17
  • Positive constraints strictly include negative constraints: any negative constraint has an equivalent all-1-colored form, but positive constraints are a strict generalization.Source: §5.1 · p. 17

5. SGs and Constrain ts: the S G C Mo del

  • A knowledge base is consistent iff its graph satisfies every constraint, and a graph query is deducible only from a consistent base; adding information can invalidate earlier deductions.Adding information to the graph can trigger a new constraint violation, leaving the knowledge base inconsistent.Source: §5.1 · p. 18, §5.2 · p. 18

5.2 Relationships with Logi s

  • For negative constraints, consistency is translated into first-order logic, and projections correspond to S-substitutions, with the converse holding for normal-form target graphs.Source: §5.2 · p. 18
  • A graph satisfies a positive constraint exactly when every application of that constraint as a rule produces a graph equivalent to the original.Source: §5.2 · p. 19

5.2 Relationships with Logics

  • For a graph satisfying a positive constraint, every graph in a derivation using that constraint is equivalent to the original graph.The section also reformulates positive-constraint violation as abductive inference from the translated background theory and observation.Source: §5.2 · pp. 19–20

5.3 Computational Complexity

  • Satisfying a negative constraint is co-NP-complete, whereas satisfying a positive constraint is NP-complete.The distinction follows from whether one must check the absence or presence of a projection.Source: §5.3 · p. 20
  • A passage fragment says work by Mugnier (2001) will be used as a basis for the proof of Theorem 12.Source: §5.3 · p. 21
  • Corollary 2 concerns deduction in SGC, but the stated result is unreadable in the supplied passage.The excerpt does not provide enough legible text to determine the corollary's conclusion.Source: §5.3 · p. 21

6. Rules and Constrain ts: S E C =S RC =S RE C

The section defines rule-and-constraint extensions in which inference and evolution rules induce distinct derivation models, then examines consistency semantics and computational complexity. It establishes undecidability results for several models and identifies more restricted cases.

6. Rules and Constrain ts: S E C =S RC =S RE C

  • Inference rules R and evolution rules E define SRC, SEC, and combined SREC models; in SREC, evolution rules move consistent worlds to new worlds.Source: §6 · p. 21, §6.1 · p. 22

6.1 De nitions and Notations

  • In SRC, every positive-constraint violation in each R-derivable graph must be R-restorable, whereas negative-constraint violations cannot be restored.Restoration may create new violations, which must themselves be shown R-restorable.Source: §6.1 · pp. 21–22

6.2 Consisten y in S RC and Logi s

  • Theorem 9’s logic-based consistency translation has a counterexample: a constraint violation can be impossible to restore.Source: §6.2 · p. 23, Figure 14 · p. 23

6.3 Unde idabilit y of the Asso iated Dedu tion Problems

  • SRC consistency and deduction, and SREC deduction, are undecidable; SEC deduction is semi-decidable.Source: §6.3 · pp. 23–24

7. De idabilit y and Complexit y of some P arti ular Cases

This section studies decidability and complexity in particular graph-reasoning cases involving rules and constraints. It examines finite expansion, range-restricted rules, and constraint forms to classify deduction and consistency problems.

7. De idabilit y and Complexit y of some P arti ular Cases

  • Under irredundant-generation assumptions, an existing closure is unique and every derivation of maximal length reaches it; any derivable full graph is also unique.The full-graph uniqueness result assumes the starting graph and graphs produced by rule applications are irredundant.Source: §7 · p. 24
  • A full graph can exist even when the closure does not.Source: §7 · p. 25

7.1 Finite Expansion Sets

  • A rule set is a finite expansion set when every simple graph can be derived to a full graph using that set.Full graphs generalize closures.Source: §7.1 · p. 25
  • If R is a finite expansion set, S_R deduction and S_RC consistency and deduction are decidable, while S_REC deduction is semidecidable.Source: §7.1 · p. 25
  • If E is a finite expansion set, S_EC deduction is decidable, but S_REC deduction remains undecidable; if R ∪ E is finite expansion, S_REC deduction is decidable.Source: §7.1 · p. 26
  • Even when R and E are each finite expansion sets, S_REC deduction is not necessarily decidable.Source: §7.1 · p. 26
  • Even though a rule set can be a finite expansion set, the closure of a graph under those rules need not exist.Source: §7.1 · p. 26
  • The word problem is encoded as SR graph deduction, with constraints restricting rule applications so that derivability tracks the word derivation.The construction first translates words and rules into graphs, then uses constraints to enforce good applications of evolution rules.Source: §7.1 · pp. 26–27

7.2 Range Restri ted Rules

  • A range-restricted rule can be decomposed into rules with one conclusion node each, preserving deduction without constraints, but this equivalence fails when constraints are involved.Source: §7.2 · p. 28
  • Range-restricted rule sets are finite expansion sets, and with bounded relation arity their derivations have polynomial length in the input size.The polynomial bound assumes the maximum arity of relation types is constant.Source: §7.2 · pp. 28–29
  • With range-restricted rules, deduction in SR is NP-complete.The theorem also gives complexity results for SRC consistency and deduction, and for SEC and SREC deduction, but their complexity symbols are not legible in the supplied passages.Source: §7.2 · p. 29
  • SREC-deduction has the same complexity class as SEC-deduction when derivation lengths are polynomial in the input size.When R is empty, SREC-deduction reduces to SEC-deduction; in the particular range-restricted case, deduction in SRC is less difficult than in SEC.Source: §7.2 · p. 30

7.3 P arti ular Constrain ts

  • With only negative constraints and no assumptions on rules in E or R, SG-consistency is co-NP-complete and SG-deduction is DP-complete.Source: §7.3 · pp. 31, 33
  • With only negative constraints, SRC-deduction and SREC-deduction remain truly undecidable, while SRC-inconsistency and SEC-deduction are semi-decidable.The theorem imposes no assumptions on the rules in E or R.Source: §7.3 · pp. 31, 33

7.3 Particular Constraints

  • Restricting constraints to negative ones lowers complexity, but problems remain undecidable when rules are involved.The passage contrasts the effect of negative constraints alone with cases that also involve rules.Source: §7.3 · p. 31
  • With range-restricted rules and negative constraints, SRC-consistency is co-NP-complete and SRC-deduction is DP-complete.The theorem’s conditions require both range-restricted rules and negative constraints.Source: §7.3 · pp. 31, 33
  • With disconnected constraints, SGC-consistency is co-DP-complete; SRC-consistency and SRC-deduction remain undecidable, though range restriction makes SRC-consistency co-DP-complete.Negative constraints are a special case of both range-restricted and disconnected constraints.Source: §7.3 · p. 33
  • With disconnected constraints, SEC-deduction remains semi-decidable and SREC-deduction remains undecidable; range-restricted rules yield completeness results for both.The supplied theorem text does not preserve the complexity classes for those completeness results.Source: §7.3 · p. 33
  • The undecidability arguments for SRC-consistency, SRC-deduction, and SREC-deduction also apply when constraints are disconnected.The passage also says SEC-deduction is semi-decidable.Source: §7.3 · pp. 34–35
  • SRC-consistency with range-restricted rules is co-DP-complete.Completeness follows from the special case where the rule set is empty.Source: §7.3 · p. 34
  • The paper derives SEC-deduction’s completeness from the special case of negative constraints.The accompanying membership claim is not recoverable from the supplied passage.Source: §7.3 · p. 34
  • The exact complexity of SGC-deduction with range-restricted constraints was not established, although it is at least DP-hard.The hardness follows from a transformation from SAT/UNSAT; the paper says an upper bound was proved but omits it.Source: §7.3 · p. 34
  • The paper leaves the complexity class of both SGC-deduction problems unassigned, while noting that they belong to an unspecified class.The class symbol is corrupted in the supplied passage.Source: §7.3 · p. 34

8. Related W orks

The section relates graph projection to constraint satisfaction and shows how mixed-CSP consistency can be represented as SG-constraint consistency. It also situates SG-constraints among conceptual-graph constraints and related reasoning frameworks.

CSP and projection

  • A CSP solution corresponds to a projection from a graph encoding its variables and constraints to a graph encoding domains and compatible tuples.The first graph represents variables as concept nodes and constraints as relation nodes; the second represents domain values and compatible tuples.Source: §8 · p. 35

CSP and SG-constraints

  • CSP can be viewed as SG-constraint consistency with an empty trigger and the graph as its obligation.Source: §8 · p. 35

Mixed-CSP

  • Mixed-CSP consistency is reducible to SG-constraint consistency by translating the mixed-CSP into graphs and a positive constraint.The constraint trigger represents the subnet induced by uncontrollable variables, and the mixed-CSP is consistent iff H satisfies C.Source: §8 · p. 37

Constraint formalisms

  • Minimal descriptive constraints generalize SG-constraints, and their consistency problem is complete for the stated complexity class.The section says the proof for SG-constraint consistency establishes this completeness result; the supplied passage does not preserve the class name.Source: §8 · p. 37

E LI RO

The discussion notes limits in relating graph projection to description logics, including projection’s inability to handle negation on primitive types. Encoding existing description logics into SG-family models is proposed as a route to new decidable classes and added type expressiveness.

Description logics

  • Projection cannot handle negation on primitive types, limiting attempts to identify larger fragments through this correspondence.Source: E LI RO · p. 38
  • Encoding existing description logics into SG-family models may identify new decidable classes and add type expressiveness to conceptual graphs.Source: E LI RO · p. 38

9. Con lusion

The paper proposes a graph-based family for representing facts, rules, and constraints, and studies the complexity of its consistency and deduction problems. It reports that models combining rules and constraints lack a global logical semantics in this account because they involve an underlying nonmonotonic mechanism.

9. Conclusion

  • The proposed family uses colored simple conceptual graphs to represent facts, inference rules, evolution rules, and constraints.Source: §9 · p. 38
  • The framework aims to keep knowledge representations and reasoning graph-based, readable, and graphically explainable to users.Source: §9 · p. 38
  • The framework integrates constraints into reasoning and systematically classifies the complexity of associated consistency and deduction problems, including restricted cases.Source: §9 · p. 38
  • The paper links consistency checking and deduction to first-order logic by translating these problems into FOL deduction.Source: §9 · p. 38
  • Models combining rules and constraints have operational semantics but no global logical semantics here, due to an underlying nonmonotonic mechanism.The authors describe defining a logical semantics for these models as an open problem.Source: §9 · pp. 38–39

Referen es

The references include work on conceptual graphs, graph-based reasoning, constraint satisfaction, and description logics.

References

  • The bibliography includes research on description logics and decidable fragments.Source: Referen es · p. 39
  • The bibliography includes foundational and survey work on conceptual graphs and graph homomorphism.Source: Referen es · pp. 39–40
  • Cited work also covers constraint satisfaction, including mixed constraints and graph-matching applications.Source: Referen es · p. 40
Loading 1106.1800v1…