# AIwiki

## Menu

## Dla Studentów

## HeKatE

## Public

- The KESE workshop
*(EN only)* - Mindstorms
*(archive)*

[[hekate:xtt2]]

**Author**: Grzegorz J. Nalepa

**Version**: Draft 2008Q3

*XTT* stands for *eXtended Tabular Trees*.
The current version proposal *XTT^2* is simply referred as XTT in this document.
It is aimed to be as the final version for the official HeKatE project (grant).

*Please put bigger remarks/discussusion, to the XTT2 development page*

XTT is a knowledge representation and design formalism for *rules*.
It serves both as a *logical* and *algebraic* specification of rules offering a concise, transparent, and efficient with respect to density factor *visual* knowledge representation form.

In contrast to traditional rulebases design approaches allowing for a *flat* (single-level) set of rules (e.g. using the Rete-based inference engines) XTT introduces an explicit *structure* in the rulebase, by introducing:

*tables*, used to represent groups of rules working in the same context (having similar structure of preconditions),*intertable links*, used to provide explicit specification of inference control, namely switching between tables, that allow for decision-tree like structure.

Each table is composed of:

- its
*scheme*or*structure*definition (provided within the first row of a table), and - the
*rules*defined by the operators and values specified in the consecutive rows.

The method is used during the phase of the logical design of the rulebase. The process of defining a table covers:

- identification of the operation context (informal),
- definition of the
*scheme*of a table, - filling it with appropriate relational operators and values in order to define specific rules.

XTT is a formal method based on an expressive logical calculus called *Attributive Logic* (or *Attribute Logic*).

mscs, regulus, kheops, ijis, ecai96, oat, dexa

XTT (also referred to as XTT1) has been first formulated by Grzegorz J. Nalepa in (gjn2004phd), and later described in (gjn2005SystemScienceXTT), and gjn2005CompSciMirella.

The version described in the above papers is referred to as XTT1.
The design was supported by the *Mirella* tool gjn2005CompSciMirella.

An important development was the supportive design method called ARD (*Attribute Relationship Diagrams*).
It was first proposed by Antoni Ligeza in (ali2005thebook), and later developed by Grzegorz J. Nalepa and Antoni Ligęza in gjn2005:kkio.

In (ali2005thebook) the family of *Attributive Logics* (AL) including SAL (*Set Attributive Logic*) has been described.
Implicitly SAL was the formal foundation for XTTv1.

In the next phase of research number of possible extensions to the base XTTv1 specification has been proposed by Grzegorz J. Nalepa, Igor Wojnicki and Antoni Ligęza, for the details see:

Recently some stronger formulation for the next version of XTT have been given in:

At this stage XTT was referred to as XTT+.
The name *GREP* (General Rule Programming) was also proposed in gjn2007inap.
The proposal was an attempt to investigate the use of the XTT+ as a general programming solution.

Originally, for XTT1 (gjn2004phd) different conceptual design methods were considered.
The ARD method was one of the considered possibilities developed by Grzegorz J. Nalepa and Antoni Ligęza in gjn2005:kkio.
Later on it has been refactored and formally described by Grzegorz J. Nalepa and Igor Wojnicki in (gjn2007flairs-ardformal).
This current version is called *ARD+*.

ARD+ is the conceptual design method considered for the XTT rule design as of the HeKatE project. However, in the future the ARD+ shall be replaced by more advanced methods.

Based on the above experiences, the current version of XTT known as XTT^2 has been proposed for the HeKatE project by Grzegorz J. Nalepa and Antoni Ligęza in 2008.
XTT^2 uses ALSV(FD) (*Attributive Logic with Set Variables over Finite Domains*) as the formal foundation.

The rules in XTT^2 are *formally* described in an *attributive language*.

The underlying logic is *Attributive Logic with Set Values over Finite Domains*, or ALSV(FD) for short.

Please read the separate ALSVFD page for details, to understand the rule formulation!

In order to provide adequate expressivity, as well as to allow for detailed implementation that provides means for formal anylysis, a detailed attribute specification approach is provided.

Please read the separate attribute specification page for the attribute specification details, to understand the rule implementation!

In general, the *logical* XTT rulebase design should be preceded by a *conceptual* design, where certain *constraints* for the XTT table headers should be specified.

Currently in HeKatE the *ARD+* conceptual rule prototyping method is supported.

- the
*input*of the method is the system description in the natural language - the
*output*of the method includes:- XTT rule prototypes in a general form on
`conditional attributes | decision attributes`

- the prototypes correspond to the XTT table schemes
- set of physical attributes present in rules
- physical attribute specification (domains, etc.).

- this specification can be provided in ARDML (HML) or in HMR (Prolog)

For more details please read the ARDplus page to fully understand the design!

Rule prototypes provide hints for XTT tables:

- structure → what attributes are in the condidtion and conclusion
- state changes in conclusion → in the value modification only attributes present in the given table may be used
- relations (inference order) → default links (table2table) can be inferred

(Please discuss at the XTT constraints page.)

To some extent they should also point to attribute communication classes.

By default we should assume that (with respect to the system as a whole) there exists:

- independent attributes (if any!) are
*input*ones, - attributes that no other dependent on, are
*output*ones, - attributes that are and have dependants are
*internal*ones.

On a general level, an XTT rule is a Rule of Inference or, more precisely, a *production rule* i.e. a basic component of any Production Rule System.

It is composed of the:

*LHS*(Left Hand Side), that is a set of premises, also named preconditions, specifying the condition under which it can be activated (fired), and*RHS*(Right Hand Side)), that is the decision, conclusion, hypothesis or action.

The *rule prototype* (or scheme) is an ordered pair `<P,C>`

, where `P`

is a tuple of conditional attribute names, present in the *premise* and `C`

is a tuple of decision attribute names.

The scheme may be precreated by the ARD+ method.

The XTT rule LHS is a *tuple of ALSV formulas*, as described in detail in syntax.

Logically, the LHS a corresponds to a *conjuction* of premises (atomic formulae of the attributive logic in use) as in the classical inference rule definition.

Any rule is assumed to be of the form:
where the admissible relational symbols in ALSV(FD) are used,
and *RHS* is the right-hand side of the rule covering the conclusion.

The current values of *all* the attributes are specified with the contents of the knowledge-base.

From logical point of view it is a formula of the form:
*Eq: state-formula*

where for simple attributes and for complex ones.

Having a table with defined rules the XTT inference mechanism searches for ones with satisfied preconditions. The satisfaction of preconditions is verified in an algebraic mode, using the dependencies specified in the first row of Table 3 (see Inference rules) for simple attributes and the first row of Table 4 (see Inference rules) for the complex ones.

The rules having all the preconditions satisfied can be fired.

See Inference for more details.

The XTT rule RHS is an ordered pair `<D,L>`

,
where `D`

is a tuple of decision formulas,
and `L`

is a *link*, that is
an ordered pair `<T,R>`

where `T`

and `R`

are table and rule-in-table IDs respectivly.

The rule RHS can contain:

- state changes, that is attribute values modifications (with use of retract/assert, by iw: there is no assert/retract anymore, assuming that attributes can be multivalued, there are only set operations, an assert is represented as a sum: assert(A(1)) ⇔ A = A u {1}), possibly with use of any predefined predicates/functions etc. for now we assume all the results are explicitly represented in state!
- external actions execution, that do not change attribute values, thus do not change the system state; these include output values definition and export,
- link that specifies inference control (e.g. a switch/case or a loop),

Attribute value modification can be done by:

1) assignement A=v where v \in D, v is a single value in case of the simple attributes, it is a set of values in case of the general attributes

2) in general , where f(State) is

2.1) ALSV(FD) formula in case of both symbolic and numeric attributes where is one of the admissible relational symbols in ALSV(FD), and the following set-theoretic operations (see Algebra of Sets: union, intersection, difference (relative complementation), complementation (absolute complementation to the domain). and V is a named set of values, or another attribute reference.

2.2) Algebraic expressions in case of numeric attributes only; the expression can contain numbers, predefined algebraic operators and functions/predicates, as well as attribute values (Prolog *is*).

3) External action specification; it contains a single predicate call, that possibly uses any attributes present in the table header as arguments.

Warning: see Inference Constraints. In the value modification only attributes present in the given table may be used!

do we need anything else as of using ALSV+ST relations to modify value? check if all alsv symbols apply!

(Please discuss at the Attribute value modification page.)

XTT rules are combined into attributive decision tables, grouping rules having the same prototypes, that is having the same conditional and decision attributes.

XTT table is composed of rows, that correspond to rules. Columns group formulas having the same attribute.

Cells can be interpreted as formulas in given rules at a given position.
A XTT cell corresponds to an *atomic formula* in ALSV(FD),
that is, it is a triple in the form of `A R V`

, where

- A is attribute name
- for simple attributes R is one of: eq, neq, in, notin
- for general attributes R is one of: eq, neq, subset, supset, sim, notsim
- V is the (multi)value to compare with.

A table provides a *visual* representation of rules, as below.

Rules in the table are interpreted one by one in a given way (see Inference), this is the Table Inference.

Table rows (rules) may be connected to other tables (rows) by links.
This forms a tree-like structure.
This is the Tree-like Inference.
(*In fact, it is more close to a graph representing a partial order of inference*).

XTT tables group rules with exactly the same schemes or prototypes.
This is why the *table scheme* (or header, prototype) is exactly the same as the rule prototype.

In order to simplify both the design and formal analysis certain types of tables are considered.

*fact*no condition (for entering information)*switch*no decision (just for inference control)*setval*only the statements are allowed in the decision, actions are also allowed (they do not change state)

In the future more types could be identified. (Please discuss at the Table types page.)

It seems that we should consider also:

*input*or*set of input cases*to be processed (states),*functional calculation*i.e. a table performing any well-defined calculation,.

This should be reconsidered with the above material on Rule RHS.

Rules are grouped into tables, depending on their attributes. Tables can be linked (row or table level). Link interpretation is:

- context change
- inference control
- process model
- partial order

This makes up a decision-tree like structure, with tables in the tree nodes. In a general case, the XTT is a directed graph, with cycles optionally allowed.

In general, rules can be fired in parallel (at least in theory) or sequentially. For the following analysis we assume the classical, sequential model, i.e. the rules are examined in turn in the top-down order and fired if the preconditions are satisfied. Various mechanisms can be used to provide a finer inference control mechanism.

In order to avoid repeated checking of preconditions a *propagation mechanism* is proposed for satisfaction and falsification of atomic formula within the table.
Let `c(i,j)`

denote the atomic formula related to the cell located in row `i`

and column `j`

.
The idea can be summarized as follows:

- once the table is defined it is searched top-down (off-line) for establishing dependencies between any atomic cell
`c(i,j)`

of rule`i`

and all the cells`c(k,j)`

(in the same column) of any rule`k`

, where`k>i`

; - in case some two cells
`c(i,j)`

,`c(k,j)`

satisfy a condition of logical consequence as specified in Table 3, a positive link`p(i,k,j)`

is established; all the links are kept in memory; in case some two cells`c(i,j)`

,`c(k,j)`

satisfy a condition of logical inconsistency as specified in Table 4, a negative link`n(i,k,j)`

is established; all the links are kept in memory; - during execution phase, if a cell
`c(i,j)`

is checked and the related atomic formula is satisfied, the truth value is propagated for the transitive closure defined with use of the positive links; the respective atoms are marked*true*and do not need to be checked in this turn; - during execution phase, if a cell
`c(i,j)`

is checked and the related atomic formula is true, the false value is propagated for the transitive closure defined with use of the negative links; the respective atoms are marked*false*and the corresponding rules are eliminated from this cycle.

This mechanism saves computational effort corresponding to repeated precondition checking and saves time in case some preconditions are logically dependent (one is logical consequence of the other or they are mutually exclusive).

In fact this can be made even more general:

- positive –> positive,
- positive –> negative (exclusion of rules),
- negative –> positive,
- negative –> negative (exclusion of rules).

This is to be reexamined and restated; a comparison to Rete may be in order.

XTT tables are connected with *links*.

A link represents a inference control mechanism. It also be thought of as a dependency mechanism, context change, process model, partial order.

Links are deterministic, that is a single rule decision can have a *single* link only.

In general we consider *positive links*, that is links that are followed where a rule is fired.

The designer can introduce *explicit negative links* by
using an explicitly defined positive construction of the following scheme:

precondtions --> conclusion| next(table.rule) true --> | else(table.rule)

We can consider introducing number of global meta-interference attributes, such as “mode_of_operation”, “task”, “did_any_rule_in_table_fired”, etc.

In general, the following *link classes* are considered:

*rule-table*(r2t) a given rule in a given table when fired, transfers control to another table, meaning the inference starts at the first rule of the destination table. This is considered the*default*for XTT^2.*rule-rule*(r2r) a given rule in a given table when fired, transfers control to another rule in another table, or possibly*the same table*(inside table link.

: iw: I'm still not convinced about rule-rule links, any advantages? There are some disadvantages though, ie: if we change the rule firing order (let's say bottom-up instead of top-down,) rule-rule links can screw us really bad. Having rule-table links only forces designer to come up with well designed conditions. So, because there are some doubts I would recommend not implementing it for time being at all.

- links can be encoded as a pair of outgoing/destination table/rule id at the rule level.
- they can represented in the Prolog rule base by the
`xtt_link/3`

predicate, having source, and destination IDs, with some optional link comment/label etc. This could be the base or additional representation to the first one.

Using the 2nd solution it would be easy to find all tables/rules on which a given rule/table depend by backward chaining.

Problem: In a general case, there might be multiple entry points in the XTT structure.

(See the discussion at the Branching page.)

*A temporary semi-parallel solution*:
ARD introduces partial order in tables,
tables can be fired in any way,
as long as this contstraint holds.

: iw: not really there might be more than one table with input attributes (or ro, rw) in the condition parts, it might be not doable to infer which table should be run first. There might be an algorithm implemented which finds an order of execution (which table to start with), but any conditions using a N/D value can screw it. I'd suggest choosing an entry table, the one that the inference process starts with, explicitly.

The XTT logic is a knowledge base executed by an inference enngine, that is the XTT rule metinterpreter, also known in HeKatE as *HeaRT*.

Some of the most basic interpreter functions are:

- interpreting XTT logic encoded in the Hekate Meta Representation,
- analyze XTT rules in XTT tables,
- provide inference control by interpreting links,
- manage the attributes by the Blackboard Architecture, by synchronizing attribute values between the system and the environment,

Extended functions, provide:

- on-line formal verification capabilities,
- on-line refinement of the XTT rule-base,
- a bridge to HQed,
- OO bridge to Java in MVC, where
*HeaRT*is the M, Java provides V, consider different approaches to C - a bridge to ANSI C
- standalone logic server with TCP
- dynamic logic serialization to Java and C

Advanced

- provide a bridge to RDBMS

Several interpreter types, or use scenarios are considered. These scenarios try to address issues such as when and how and how many times is the interpreter run.

Currently only the simplest one is described.

The *Single Pass* interpreter is the simplest scenario:

- the interpreter is executed externally by the user, system, etc.
- input attribute callbacks provide input facts
- the inference starts
- initial branching is handled
- links are followed
- inference process ends
- output attribute values can be sent by callbacks

For sanity, it should be assumed, that no attributes input/communication attributes are updated during the inference.

Here we can think about a *transaction-like mode* and possible *attribute freezing* or more lively models. Various possibilities of separation both among tables and tables vs. environment can be considered.

This is the basic mode, that should be considered, implemented, and analyzed before any other options.

For other modes see Interpreter Scenarios.

The following assumptions for system modeling with ALSV rules is given:

- the system is modeled with the use of attributes (state variables!),
- the state of the system is fully described with attribute values,
- rule firing can possibly change system state by changing attribute values,
- rules can execute actions external to the system,
- it is assumed that these actions do not change system state,
- the state can be changed from the outside.

Perspectives:

- controller vs. object
- decision system (information system) vs. physical system (subject of decision)
- system vs. environment

It could be summarized, that “communication” between the system and the world is conducted using attributes and their values.

Attributes are considered *shared resources*.

The XTT logic can access the attribute values in the XTT tables.

The values can be accessed from the outside of the system/interpreter (from the environment).

The values are modified/updated by both the environment and the system simultaneously.
A simple locking/semaphore approach is exercised.
This approach should be *independent* of the intepreter scenarios!

The access and update policy depends on the attribute class.

Several attribute classes are considered:

- input (S ← E),
- output (S → E),
- internal (S → S), (was
`middle`

in XTTv1) - communication (comm) (S ↔ E)

Arrows indicate the System/Environment interaction.

: iw: what's happened to `ro, rw, wo, state`

classes?

Discuss ideas here: Attribute Classes.

The actual value modification is provided by a middle layer of attribute callbacks. For now it is assumed that a callback is a predicate run by the intepreter to pull (input) or push (output) attribute values.

If an asynchronous interpreter mode is considered attribute locking should be provided during update.

During the implementation discuss experiences here: Attribute Callbacks.

The following textual algebraic representation is provided. It is to be generated by the design tool (e.g. HQed) and directly run by HeaRT.

Table scheme, logically also rule prototype.

xttscheme: [a1,...,an], [h1,...,hm].

Rule:

xttrule: [Table, Id]: [c1,...,cn] then [d1,...,dn], [Table, Id].

Fact:

XTT on ALSV allows for a formal analysis of important system properties during the logical design, e.g.:

- consistency, and
- completeness

Appropriate algorithms for XTT^2 should be developed.

In general, there are at least the follwoing possibilities:

- rule-rule (pairwise) analysis (e.g. identical rules, subsumption, exclusive rules - determinism),
- rules-in-table (all) analysis (e.g. local, contextual completeness, determinism),
- chains-of tables/rules analysis (unprovided facts, unused conditions, unreachable conclusions, etc.).

Further, any path should be analyzed for *calculability* or *executability*, i.e. if it can be followd (no part of information is missing) and – if parallel action are allowed – for determinism and deadlocks.

For now see the Hekate Markup Language.

see for s in this page.

VARDA should generate:

- prototypes in HMR
- default links
- physical attribute communication class

Selected:

- high knowledge density
- transparent representation
- visual scalability

hierarchical types, e.g. `temp1`

is a the same as `temp`

but with restricted range
is this too redundant?

Blocks, as simulink boxes to simplify the design.

This could be possibly cobmined with the so-called *scope* from the XTT+.

If it is of ANY use?

- direct AVR
- grouped atts
- hybrid opps

From XTT to BPMN and back again

declarative inference control spec

This perhaps we should leave as a *research thread* only.

Fixed, simple declaration of control inference (with a few parameters only + the links) should be sufficient to demonstrate the power of XTT!

On the other hand we have to re-think the problems and advanatges of using cut (!) and similar mechanism (e.g. fail, exit).