Towards a Knowledge Compilation Map for Heterogeneous Representation Languages

1 Introduction

There exist myriads of representation languages, with different capabilities; each one fits some applications, but is not suitable for others-there can be no best language. Choosing a good language for a given application is thus a fundamental problem in AI. Levesque and Brachman [1985] have shown that this problem boils down to a compromise between (computational) efficiency and expressiveness; for languages of equal expressiveness, efficiency must be balanced against succinctness [Gogic et al., 1995]. The knowledge compilation map [Darwiche and Marquis, 2002] relies on these aspects to compare languages representing Boolean functions.

However, there are few works about the comparison of "heterogeneous" representation languages, based on different interpretation domains. It is well-known that ordered multivalued decision diagrams (OMDDs) [Srinivasan et al., 1990] can be transformed in polynomial time into ordered binary decision diagrams (OBDDs) [Bryant, 1986], using for example a log encoding (see Figure 1); these languages are considered somewhat equivalent. Yet, because of the specificity Pierre Marquis and Alexandre Niveau CRIL-CNRS, Univ. Artois Lens, France {marquis,niveau}@cril.fr of existing frameworks, this "equivalence" cannot be formally stated, and its use in proofs requires much prudencewe would like to use it as an elementary brick to infer results in an automated fashion. It can be noted that when the notion of a "representation language" is used in a broad sense, e.g., in surveys of the knowledge representation or artificial intelligence domains [Brachman and Levesque, 2004; van Harmelen et al., 2008; Russell and Norvig, 2010], it is only described informally; and whenever there is a need for a formal definition, its scope is restricted to the case in point.

⇤This work is partially supported by the project BR4CP ANR11-BS02-008 of the French National Agency for Research.

In this paper, we propose a generalized formal framework for representation languages, including a definition of equivalence suitable for heterogeneous languages, with the longterm purpose of casting them in a single knowledge compilation map. We prove that several properties usually expected in specific maps still hold in our general view, modulo certain modifications. We begin with a formal definition of a "representation language" and of important related notions, such as completeness and sublanguage, in Section 2. Then, we show how the usual concepts used for language comparison in the knowledge compilation map can be generalized to heterogeneous languages: Section 3 deals with notions related to representation efficiency (expressiveness, succinctness, polynomial translation), and Section 4 with notions related to computational power (notably queries and transformations). Section 5 concludes the paper, and illustrates a practical use of our framework on a case study (that of MDDs and BDDs). 1

2 Representation Language

2.1 Definitions

The knowledge compilation (KC) map is built upon the notion of language; it was not formally defined in the original map [Darwiche and Marquis, 2002], because it implicitly had the classical meaning of a formal language, i.e., a set of words over an alphabet. This "language" terminology only refers to syntax; semantics is given by an implicit interpretation function (that of propositional formulæ). There is also a natural hierarchy on languages, namely inclusion: a sublanguage, or fragment, is simply a subset of a language.

In this classical setting, most features of languages are thus implicit, including their interpretation function and their

1 Proofs are omitted, but an extended version is available at <url: http://www.cril.univ-artois.fr/~niveau/publis/IJCAI13_FMN.pdf>.

>

>

?

>

?

Figure 1: An ordered interval automaton (OIA), an ordered multivalued decision diagram (OMDD), and an ordered binary decision diagram (OBDD). The OMDD is a discretization of the OIA, using partitions ¶[0↪3▷45]↪(3▷45↪5▷1)↪ [5▷1↪8]↪(8↪10]♦ for x and ¶[0↪ 2)↪ [2↪ 4▷6]↪ (4▷6↪ 7▷7]↪ (7▷7↪ 10]♦ for y. The OBDD is obtained from the OMDD by log encoding.

hierarchy, but also the notion of completeness and the domains of variables. This crucial limitation prevents one from directly applying this framework to a more general setting. Consider the bit sequence 10101010: interpreted as a binaryencoded natural integer, it corresponds to 170; as the "signand-magnitude" encoding of a relative integer, to -42; as a fixed-point real number, to 10▷625; etc. These languages have the same syntax, but different interpretation functions. Our definition of a representation language builds upon that of Fargier and Marquis [2009], in that we use an explicit semantics; but we relax their assumption that it is restricted to the representation of Boolean functions, and consider languages that can represent potentially anything. For that purpose, let U be our universe of discourse, containing at least all "objects" that our languages aim at representing, notably real and natural numbers, Boolean functions, 2 etc. We also use a generic alphabet S, that we suppose countably infinite; we call formula a word over this alphabet, i.e., an element of S ⇤ . 3 Now, at the highest level of abstraction, a representation language is a relation linking formulæ and objects in the universe.

Definition 2.1 (Representation language). A representation language is an ordered pair L = hFL↪ILi, where FL ✓ S ⇤ is a set of formulæ called the syntax of L, and IL, called the semantics of L, is a many-to-one relation IL ✓S ⇤ ⇥U that is defined at least on all formulæ in FL.

The semantics of a language is a way of interpreting the symbols in S; it can be seen as a function 4 from FL to U, mapping any formula j in the syntax of L (called an Lrepresentation) to its interpretation Jj K L . For example, the language of propositional logic can be defined as PROP = hFPROP↪IPROPi, with FPROP the set of well-formed formulæ (with connectives restricted to ≻, _, and ^) and IPROP the usual inductive interpretation function, associating with each This semantics is used in lots of languages, such as CNF = hFCNF↪IPROPi (with FCNF the set of formulæ in conjunctive normal form) or HORN-C = hFHORN-C↪IPROPi, (with FHORN-C the set of Horn-CNFs). Other examples include BDD, MDD, and IA, the languages of binary and multivalued decision diagrams and of interval automata [Niveau et al., 2010] (see Figure 1), and the language of algebraic decision diagrams, ADD [Bahar et al., 1997]. For space reasons, the paper is focused on these languages (in particular, the relationship between the MDD and BDD families is presented in Section 5), but the framework is much more general. 5

formula j its corresponding Boolean function Jj K PROP 2 B. 2 We denote as B the set of Boolean functions of Boolean variables, and as B andB the sets of Boolean functions of variables having respectively an integer and a real domain.

3 We use the Kleene star to denote unbounded Cartesian product: S⇤ = Si2 S i (we consider words as tuples of symbols from S).

4 In Def. 2.1, we use a many-to-one relation instead of a partial function to simplify later notation. The many-to-one requirement is not necessary (ambiguous semantics can be useful, a good example being natural languages) but we adopt it for the sake of simplicity.

Remark that there can be elements w 2 U with which IL does not associate any formula, neither inside FL nor outside. Those elements are thus completely unrelated to the language; for example, IPROP ignores any object that is not a Boolean function. The elements of U with which IL associates at least one formula are called L-interpretations.

Definition 2.2 (Interpretation space). The interpretation space of a representation language L, denoted WL, is the codomain of IL, i.e., WL = ¶w 2 U ♣ 9j 2 S ⇤ ↪j IL w ♦.

Since CNF and HORN-C have the same semantics, they also have the same interpretation space, which is B. Note that elements in the interpretation space of a language L are not guaranteed to have a representation in FL; e.g., the syntax of HORN-C is not expressive enough to cover the whole interpretive power of its semantics-the language is incomplete.

Definition 2.3 (Completeness). A representation language L is complete if and only if 8w 2 WL↪ 9j 2 FL↪ Jj K L = w. 2.2 Sublanguages

A representation language is not simply a set of formulæ, therefore the notion of sublanguage cannot simply be based on a restriction of syntax, as it is in the classical KC map.

Definition 2.4 (Sublanguage). Let L and L0 be two representation languages; L0 is a sublanguage of L, denoted L0 ✓ L, if and only if FL0 ✓FL and IL0 ✓ IL. Moreover, if L0 ✓ L and IL0 =IL, L0 is said to be a fragment of L.

5 It notably includes VNNF [Fargier and Marquis, 2007], and languages outside the usual scope of KC, like all flavors of constraint networks (discrete or continuous, weighted, fuzzy, etc.) [see, e.g., Rossi et al., 2006], quadtrees [Finkel and Bentley, 1974], R? - trees [Beckmann et al., 1990] and, with appropriate interpretation spaces, first-order logic, ontologies, programming languages, etc.

The condition that all formulæ in the sublanguage must respect the syntax of the parent language remains; but they must also respect its semantics (which was implicit in the classical framework). Note that our definition of a representation language distinguishes two kinds of sublanguage hierarchies, that of fragments, which orders languages of a fixed semantics, and that of the generalized sublanguages, in which even heterogeneous languages can be compared: e.g., it holds that OBDD ✓ OMDD ✓ OIA, since OBDDs are specific OMDDs (restricted to Boolean variables), and OMDDs are specific OIAs (restricted to discrete variables). This natural property cannot be formally stated within the classical KC map.

It is interesting to notice that contrary to what is usually expected, incompleteness is not inherited by sublanguages. Thus, OIA is not complete (edge labels are restricted to closed intervals), but OBDD is, although OBDD ✓ OIA. This comes from the fact that completeness is relative to the interpretation space of the language, which is not necessarily the same in a sublanguage. The expected property actually holds on fragments, which have stronger requirements.

Proposition 2.5. Let L be a representation language, and L0 a fragment of L. If L0 is complete, then L also is.

2.3 Operations on Languages

In the classical KC map, the hierarchy of fragments is induced by a set of syntactic properties verified by languages: considering only read-once BDDs yields FBDD, adding ordering yields OBDD, etc. These can be seen as syntactic restrictions; they can reduce expressiveness, since the interpretation space does not change. On the other hand, the hierarchy of decision diagrams in the broad sense (OBDD ✓ OMDD) cannot be generated by only restricting syntax, since some interpretations must be removed: it can be built using semantic restrictions.

Definition 2.6 (Language restrictions). The (syntactic) restriction of a language L to a set of formulæ F ✓ S ⇤ is the fragment L♣F = hFL \F↪ILi .

h¶j 2FL ♣ Jj K L 2W ♦↪IL \(S ⇤ ⇥W)i . Using this definition, HORN-C is the syntactic restriction of CNF to Horn-CNFs, for example, while BDD is the semantic restriction of MDD to functions of Boolean variables. Another way of building a language is to combine existing languages.

The (semantic) restriction of a language L to an interpretation space W ✓ U is the sublanguage L♣W =

Definition 2.7 (Union and intersection). The union of two languages L and L0 is L[L0 = hFL [FL0 ↪I [ I 0 i, and their intersection is L\L0 = hFL \FL0 ↪ I \ I 0 i.

This allows for example to formally state that BDD = MDD\ ADD, which expresses the fact that BDDs are both exactly the MDDs on Boolean variables, and the ADDs with two leaves.

We are now ready to define the usual concepts of the KC map: expressiveness, succinctness, and polynomial translatability, and support of queries and transformations.

3 Representation Efficiency

In the KC map, expressiveness has a fundamental role: a difference in succinctness between two languages is only significant if they have the same expressiveness. Languages with different interpretation spaces are a fortiori not compared in the map. Yet, there are works about translations between heterogeneous languages [Walsh, 2000; Gottlob, 1995], and it would be interesting to cast known results in the map. This calls for a more general definition of expressiveness, succinctness, and polynomial translatability, that would not require a strict equality of interpretations, but only their equivalence modulo some semantic correspondence, i.e., some relation linking the two heterogeneous interpretation spaces-which induces a translation between formulæ.

Definition 3.1 (Semantic correspondence, translation). A semantic correspondence between two interpretation spaces W1 and W2 is a subset of W1 ⇥W2. We will call translation from L1 to L2 a semantic correspondence T ✓WL1 ⇥WL2 .

Examples of well-known translations include the various encodings of discrete constraint networks into propositional formulæ [Walsh, 2000], such as the direct encoding Tdir and the log encoding Tlog, which associate functions in B with functions in B; or the discretization translation Tdiscr, which relates a continuous constraint network with the discrete constraint networks it can be discretized into. We also use the generic identity translation Id, which denotes any relation ¶hw↪wi : w 2 W♦ with W ✓ U, in a slight abuse of notation.

3.1 Expressiveness and Succinctness

A first criterion for the comparison of representation languages is their relative expressiveness [Gogic et al., 1995; Fargier and Marquis, 2008]. When they have the same semantics, expressiveness compares their ability to represent objects. However, we want to compare languages of different semantics, therefore we will define expressiveness as depending on a semantic correspondence, and similarly extend relative succinctness [Gogic et al., 1995; Darwiche and Marquis, 2002], which compares the ability of languages to represent objects compactly.

Definition 3.2 (Expressiveness, succinctness). Let L1 and L2 be two languages, and T a translation from L1 to L2.

exists an L2-representation j2 such that Jj1 K L1 T Jj2 K L2 . L2 is at least as succinct as L1 modulo T , denoted L1 ≥Ts L2, if and only if there exists a polynomial P(·) such that for each L1-representation j1, there exists an L2-representation

L2 is at least as expressive as L1 modulo T , denoted 6 L1 ≥Te L2, if and only if for each L1-representation j1, there

j2 such that ♣j2♣ P(♣j1♣) and Jj1 K L1 T Jj2 K L2 . Comparable expressiveness is necessary for a translation to be well-adapted to the comparison of two languages. It is clearly not a sufficient condition: for any two languages L1 and L2, the trivial translation T =WL1 ⇥WL2 verifies L1 ≥Te L2, yet it does not allow one to infer any result about L1 and L2. Sufficient conditions will be studied in Section 4.

As in the classical KC framework, succinctness is a refinement of expressiveness: L ≥Ts L0 =) L ≥Te L0 . However, while this implies that the classical succinctness relation, which corresponds to ≥Id s , is not very informative when applied to heterogeneous languages, our generalization does not suffer from this drawback: it is possible to formally state succinctness results like MDD ⇤Tdir s CNF. Note that we can apply the KC notation to any representation language: for example, denoting RADIXn the language of natural integers represented in radix n, it is well-known that RADIX1 >Id s RADIX2, and that for any n > 1, RADIXn ⇠Id s RADIX2.

6 We also use (i) L1 Te L2 to mean L2 ≥T -1 e L1, (ii) L1 ⇠Te L2 to mean that both L1 ≥Te L2 and L1 Te L2, and (iii) L1 >Te L2 to mean that L1 ≥Te L2 but L1 ⇥Te L2. This notation applies, mutatis mutandis, to succinctness and polynomial translatability.

Note also that specific translations can be used to compare the succinctness of languages having the same interpretation space but different expressiveness. For example, languages HORN-C and KROM-C = hFKROM-C↪ IPROPi, where FKROM-C is the set of 2-CNF formulæ, are incomparable with respect to ≥Id e , therefore they are also incomparable with respect to classical succinctness ≥Id s ; however, it can be interesting to know which one is the most succinct when restricted to those Boolean functions that both can represent. It is possible to express this within the generalized framework, defining an ad-hoc translation T , for which HORN-C ≥Ts KROM-C holds if and only if every HORN-C-representation is either not representable in KROM-C, or representable in polynomial size. 7

3.2 Polynomial Translatability

Succinctness requires the existence of a polynomial-size translation, but not the existence of an algorithm building it, let alone its tractability. The last refinement of expressiveness is polynomial translatability [Fargier and Marquis, 2009].

Definition 3.3 (Polynomial translatability). Let L1 and L2 be two representation languages, and T a translation from L1 to L2; L1 is polynomially translatable into L2 modulo T , denoted L1 ≥Tp L2, if and only if there exists a polynomialtime algorithm mapping any L1-representation j1 to an L2representation j2 such that Jj1 K L1 T Jj2 K L2 . Moreover, if the output is guaranteed to be at most polynomially smaller than the input, that is, if there is a polynomial P(·) such that for any j1, the output j2 verifies ♣j1♣  P(♣j2♣), then the translation is said to be stable, and we denote L1 ≥Tp⇠ L2.

It holds, for example, that OMDD≥Tdir p⇠ OBDD and OMDD ≥Tlog p⇠ OBDD [Srinivasan et al., 1990] (e.g., in Figure 1, the OBDD results from the log encoding of the OMDD). The stability condition is generally not hard to achieve; in particular, it discards special cases in which the translated formula is exponentially smaller than the original one.

In the classical KC framework, polynomial translation corresponds to ≥Id p , and has important consequences on the satisfaction of queries and transformations. For example, denoting MODS the restriction of PROP to smooth and deterministic DNFs [Darwiche and Marquis, 2002], the fact that MODS ≥Id p OBDD (i.e., MODS-representations can be transformed into equivalent OBDDs in polynomial time) implies that MODS supports all queries supported by OBDD; and since NNF ⇠Id p PROP (propositional formulæ with connectives limited to ≻, _, and ^ can be put in negation normal form in polynomial time), NNF and PROP support the exact same set of queries and transformations. In the latter case, the two languages are hence considered as strictly equivalent. However, these properties do not hold when a translation is used, because queries and transformations applying to one language do not necessarily apply to the other. For example, OIAs can be discretized into OMDDs (e.g., in Figure 1, the OMDD is a discretization of the OIA), i.e., OIA ≥Tdiscr p OMDD, but while OMDD supports model enumeration, OIAs generally have an infinite number of models. Conditions under which this kind of inference is possible are studied in Section 4.

7 One can define T as the set of pairs of Boolean functions h f ↪gi 2B 2 for which if g has a KROM-C-representation, then f = g.

3.3 Properties of Comparison Relations

Let ≥ denote any of the three relations we have defined, ≥e, ≥s, or ≥p. Using the Id translation, we recover the original definition of each relation; ≥Id is suitable only to homogeneous languages, but has the advantage of being a preorder. It is not the case for any T , simply because interpretation spaces can be different (in which case ≥T notably cannot be reflexive). However, when T is an endorelation, ≥T inherits some of its properties.

Proposition 3.4. Let W ✓ U, and T ✓W 2 . If T is reflexive (resp. transitive), then ≥T is also reflexive (resp. transitive).

Such translations can be used to compare languages over the same interpretation space, as shown with HORN-C and KROM-C. When T has no remarkable property, the next proposition nevertheless expresses a kind of "pseudo-transitivity".

Proposition 3.5. If, for some representation languages L1, L2, and L3, and some semantic correspondences T and T 0 , it holds that L1 ≥T L2 and L2 ≥T 0 L3, then L1 ≥T 0 ◦T L3 (where ◦ denotes the composition of relations).

This proposition has a useful corollary, allowing succinctness results in a given fragment hierarchy to be extended to another, granted that a "reversible" polynomial translation exists between them (see Section 5 for an example).

Corollary 3.6. Let L1 and L2 (resp. L01 and L02 ) be two languages of interpretation space W (resp. W 0 ). If there exists a bijective correspondence T between W and W 0 such that L1 T L01 and L2 ≥T L02 , then L1 ≥Id L2 =) L01 ≥Id L02 .

4 Computational Power

Representation languages are used to solve problems about the objects they represent. A solution to a problem is generally found thanks to an algorithm, that is, a sequence of operations on the objects; the practical implementation of the algorithm depends on the chosen representation languages.

4.1 Operations

Definition 4.1 (Semantic operation). A semantic operation on a universe W ✓ U is a piecewise total 8 relation r ✓ W k ⇥P ⇥A , where P ✓ U and A ✓ U are sets containing parameters and answers respectively, and either k 2 (the semantic operation is then bounded), or k = ⇤ (the semantic operation is then unbounded).

8 A relation R✓ D1 ⇥· · ·⇥Dn is piecewise total if and only if 8i 2 ¶1↪ ▷ ▷ ▷ ↪n♦↪8di 2 Di↪9hr1↪ ▷ ▷ ▷ ↪rni 2 R↪ri = di. Less formally, this means that its projection on each of its dimensions is total.

Let us give examples based on the KC map, with W the set of Boolean functions of real variables: W = B . The operation associated with the "conditioning" transformation is the partial function rCD from W ⇥( )⇤ to W, defined as rCD : h f ↪ #- x i 7! f ♣ #- x (with rCD only defined on pairs h f ↪ #- x i such that f is defined on #- x ). Here k = 1, P = ( )⇤ is the set of all assignments, and A =W is the set of Boolean functions. The operation associated with the "model extraction" query is not a function, but a relation rMX associating any Boolean function f with all of its models; here k = 1, A =( )⇤ , andP is ignored. 9 The operation associatedwith the "conjunction" transformation is the mapping r^C : h f1↪ ▷ ▷ ▷ ↪ fnk i 7! Vnk i=1 fi for any nk 2 . Here, the operation is unbounded: k = ⇤.

The complexity of a semantic operation r ✓ W k ⇥P⇥A depends on the representation languages considered. The most important one is the "input" language, that is, the language representing elements of W. Semantic operations can be much more generic than needed: the operations presented above apply to all Boolean functions of real variables, but they can also be used, in a more restricted fashion, to compare Boolean functions of Boolean variables. A semantic operation can indeed be applied to a subset W 0 of its universe: we denote r♣W 0 the largest (with respect to inclusion) semantic operation verifying r♣W 0 ✓ r \(W 0k ⇥P⇥A ), and PW 0 and AW 0 the sets of parameters and answers of r♣W 0 , from which all "superfluous" elements have been removed. We will say that a semantic operation on W ✓ U is applicable to a language L when WL ✓W holds: for example, rCD is applicable to CNF, and thenPWCNF is the set of Boolean assignments and AWCNF the set of Boolean functions of Boolean variables. We use this notion of application to define the syntactic operations that are associated with semantic operations.

Definition 4.2 (Operation). A (syntactic) operation is a tuple O = hr↪L↪PRM↪ANSi such that (i) r is a semantic operation: r ✓W k ⇥P⇥A ; (ii) L is a representation language to which r is applicable: WL ✓ W; (iii) PRM is a representation language covering all parameters compatible with L: PWL ✓WPRM; (iv) ANS is a representation language covering all answers compatible with L: AWL ✓WANS.

Note how the choice of the main representation language in the syntactic operation restricts the semantic operation. When choosing L, we discard all elements in the domain of r that are not L-interpretations. Languages in an operation induce a syntactic version of its underlying semantic operation.

Definition 4.3 (Complexity of an operation). Let O = hr↪ L↪ PRM↪ ANSi be a syntactic operation, with r ✓ W k ⇥P⇥A . The problem associated with O is the following: for any tuple hj1↪ ▷ ▷ ▷ ↪jnk ↪pi of formulæ from F k L ⇥FPRM, compute a formula a 2 FANS such that hJj1 K L ↪ ▷ ▷ ▷ ↪Jjnk K L ↪Jp K PRM ↪ Ja K ANS i 2 r, if there exists one. The complexity of O is that of its associated problem.

It is the complexity of this syntactic problem that defines the complexity of the corresponding operation. Thus, "operation O is in polynomial time" means that there exists a polynomial-time algorithm that solves the problem associated with O. An operation is hence a way of specifying a problem; classical decision problems in computability theory constitute a special case of operations. A decision problem can be modeled as O = hrF↪S ⇤ ↪booli, where rF is the indicative function of a formal language F, and bool the representation language associating the symbol "0" with ? and the symbol "1" with >. More generally, an operation allows one to express a function problem without losing the semantics.

9 When a semantic operation needs no parameter, we omit P for simplicity (we implicitly consider that it is a singleton).

4.2 Queries and Transformations

We recover queries and transformations as special operations by fixing some elements, namely, languages and complexity.

Definition 4.4 (Query, transformation). A query (resp. a transformation) is a tuple Q= hr↪PRM↪ANSi (resp. T = hr↪ PRMi) such that for any representation language L to which r is applicable, OQ↪L = hr↪L↪PRM↪ANSi (resp. OT↪L = hr↪L↪ PRM↪Li) is an operation. Language L supports Q (resp. T) if and only if OQ↪L is in input-output polynomial time (resp. OT↪L is in polynomial time).

For languages representing Boolean functions, denoting term the language of conjunctions of atoms of the form [x = n] (where x 2 S is a variable and n 2 ), the model extraction query can be defined as MX = hrMX↪termi, the conditioning transformation can be defined as CD = hrCD↪ termi, and the conjunction transformation as ^C = hr^Ci. These operations apply to any language representing Boolean functions, be it restricted or not to a subset of this space, e.g., to functions of Boolean or integer variables.

Support of given queries and transformations is an indicator of the absolute and relative computational power of representation languages; with our definition, the concept applies universally to any representation language. However, it should be clear that the actual list of queries and transformations useful to compare a given hierarchy of languages generally depends on their interpretation space. Nevertheless, it is sometimes possible to infer results about queries and transformations on a hierarchy from results on another hierarchy; e.g., support of most queries and transformations for languages in the MDD family can be inferred from results on the BDD family, because these families are polynomially equivalent modulo a "suitable" translation. We will now present sufficient conditions for this kind of inference to be possible.

4.3 Operations and Polynomial Translation

In the general case, we are interested in deducing the tractability of an operation O from the tractability of another, into which O can be translated. We start by defining the notion of translation between two semantic operations.

Definition 4.5 (Semantic operation translation). Let r1 and r2 be two semantic operations: r1 ✓W k 1 ⇥P1⇥A1 and r2 ✓ W k 2 ⇥P2 ⇥A2. A semantic operation translation from r1 to r2 is a triple hTW↪TP↪TA i, where (i) TW ✓W1 ⇥W2, (ii) TP ✓P1 ⇥P2, and (iii) TA ✓ A1 ⇥A2, that verifies r1 = T -1 A ◦r2 ◦(T k W · TP), where ◦ (resp. ·) denotes the composition (resp. product) of relations.

We begin to see why some translations are more useful than others: for example, the trivial semantic correspondence T =W1⇥W2 is not likely to be used in a semantic operation translation. The interest of having L1 ≥Tp L2 actually depends on how this specific T relates to the operations considered. Moreover, nothing can be deduced if the translation of parameters and answers is not tractable: we need the notion of polynomial translation between syntactic operations.

Definition 4.6 (Polynomial translation between operations). Let O1 =hr1↪L1↪PRM1↪ANS1i and O2 =hr2↪L2↪PRM2↪ ANS2i be two operations. We say that O1 is polynomially translatable into O2 if and only if there exists a semantic operation translation hTW↪TP↪TA i from r1 to r2 verifying (i) L1 ≥TW p L2; (ii) PRM1 ≥TP p PRM2; and (iii) ANS1 TA p ANS2. If the polynomial translation between answer languages is stable, that is, if ANS1 TA p⇠ ANS2, then the translation between operations is said to be answer-stable.

This notion encompasses the familiar polynomial manyone reduction of computational complexity theory: a problem, i.e., an operation O1 = hrF1 ↪S ⇤ 1 ↪booli, is polynomialtime many-one reducible to another, i.e., to an operation O2 = hrF2 ↪ S ⇤ 2 ↪booli, if and only if O1 is polynomially translatable into O2. In a fashion similar to reductions between problems, the tractability of an operation depends on that of operations into which it can be polynomially translated.

Theorem 4.7. Let O1 and O2 be two operations such that O1 is polynomially translatable into O2. If O2 is in polynomial time, then O1 is in polynomial time. When the translation is answer-stable, it holds that if O2 is in input-output polynomial time, then O1 is in input-output polynomial time.

By this theorem, hrMX↪MDD↪termi, hrCD↪MDD↪term↪MDDi, and hr^C↪MDD↪MDDi are tractable, relying on the tractability of the corresponding operations on languages of the BDD family. However, the fact that OBDD supports SFO (the forgetting of a single variable) does not imply that OMDD supports SFO, because forgetting a multivalued variable boils down to forgetting an unbounded number of Boolean variables, which is NP-hard on OBDD. Similarly, translations that do not maintain the number of models cannot be used to infer that OMDD supports CT from the fact that OBDD supports CT. Note that the condition of answer-stability is necessary for the second statement of the theorem to hold, because the time complexity of the overall procedure depends on the size of O2's answer, which can be exponential in the input.

The deductions allowed by this theorem can pertain to very disparate operations. However, in the context of a KC map, the setting is generally more restricted: typically, one has found a semantic correspondence between two interpretation spaces, inducing a polynomial translation between languages in the two hierarchies, and would like to make deductions such as "if L supports this query, then L0 also supports it"; i.e., one is interested in a single semantic operation applicable to both languages. This can actually be cast as a corollary of Theorem 4.7, as long as one considers only queries and transformations that are suitable to the given translation.

Definition 4.8 (T -suitability). Let T be a semantic correspondence between some W1 ✓ U and some W2 ✓ U. A query Q = hr↪PRM↪ANSi is T -suitable if and only if: (i) r is applicable to W1 and W2; (ii) there exist two semantic correspondences TP and TA such that hT ↪TP↪TA i is a translation from r♣W1 to r♣W2 ; (iii) PRM♣PW1 ≥TP p PRM♣PW2 ; (iv) ANS♣AW1 TA p⇠ ANS♣AW2 . A transformation T= hr↪PRMi is T -suitable if and only if it verifies conditions i-iii, with TA=T (the last condition does not apply, since there is no ANS language in a transformation).

Most queries and transformations of the classical KC map are suitable to direct and log encoding, including MX, CD, ^C, and those considered by Darwiche and Marquis [2002]- with the exception of SFO, for reasons stated earlier. This is particularly interesting with regard to the following result.

Theorem 4.9. Let L1 and L2 be two representation languages, and T a translation from L1 to L2. If L1 ≥Tp L2, then every T -suitable query supported by L2 is also supported by L1. If L1 ⇠Tp L2, then every T -suitable query or transformation supported by L2 is also supported by L1.

This allows to automatically extend most known results about BDDs to MDDs, and more generally, most results from the Boolean KC map to languages over non-Boolean variables. Note however that results are not exactly the same, as they depend on the suitability of each query and transformation to the translation considered; thus, OMDD does not support SFO [Amilhastre et al., 2012], even though OBDD does.

5 Conclusion

In this paper, we have presented a framework for comparing representation languages. While taking as few hypotheses as possible about what constitutes an admissible representation language, we showed how the usual concepts of the knowledge compilation map could be adapted to this broader setting, allowing the comparison of heterogeneous languages with respect to their representation efficiency and their computational capabilities, and the exploitation of known results in the Boolean case to numerous languages, over discrete or continuous variables and non-Boolean valuation.

As an illustration of the latter point, let us take the simple example of the "bounded MDD" family: we define the k-MDD language as the restriction of MDD to variables with domains of cardinality k, and its fragments k-FMDD, k-OMDD, and k-OMDD< as its restriction to read-once, ordered, and <-ordered diagrams [Darwiche and Marquis, 2002], respectively.

Proposition 5.1. It holds that k-MDD<s k-FMDD<s k-OMDD<s k-OMDD<, and each of the queries and transformations considered by Darwiche and Marquis [2002] is supported by k-MDD (resp. k-FMDD, k-OMDD, k-OMDD<) if and only if it is supported by BDD (resp. FBDD, OBDD, OBDD<).

This proposition follows directly from the fact that k-MDD ⇠Tk p BDD, k-FMDD ⇠Tk p FBDD, k-OMDD ⇠Tk p OBDD, and k-OMDD< ⇠Tk p OBDD<, denoting Tk the restriction of Tdir to variables with domains of cardinality k, by applying Corollary 3.6 (Tk is bijective) and Theorem 4.9 (all queries and transformations defined by Darwiche and Marquis [2002] are Tk-suitable), respectively.

This is a first step towards a generalized knowledge compilation map, in which heterogeneous language hierarchies could be presented in a unified way.