--- hekate:xtt2 [2008/11/17 23:48]
gjn
+++ hekate:xtt2 [2019/06/27 15:49] (current)
@@ Line 3: / Line 3: @@
 **Author**: Grzegorz J. Nalepa
-//Version:  Draft 2008Q3//
+**Version**:  Draft 2008Q3
 //XTT// stands for //eXtended Tabular Trees//.
@@ Line 9: / Line 9: @@
 It is aimed to be as the final version for the official HeKatE project (grant).
+//Please put bigger remarks/discussusion, to the [[hekatedev:xtt2|XTT2 development page]]//
 ===== Introduction =====
 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 rulebase design approaches (e.g. using the Rete-based engines) XTT introduces an explicit //structure// in the rulebase, by introducing:
+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 group rules working in the same context,
+  * //tables//, used to represent groups of rules working in the same context (having similar structure of preconditions),
-  * //intertable links//, used to provide inference control between tables, that allow for decision-tree link structure
+  * //intertable links//, used to provide explicit specification of inference control, namely switching between tables, that allow for decision-tree like structure.
-The method is used in the phase of the logical design of the rulebase.
-XTT is a formal method based on an expressive logical calculus called //Attributive Logic//.
+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//).
 ==== History and Related Documents ====
-XTT (also referred to as XTT1) has been first formulated by Grzegorz J. Nalepa in [[hekate:hekate_bibliography#gjnphd|(gjn2004phd)]], and later described in [[hekate:hekate_bibliography#gjn2005sysci:xtt|(gjn2005SystemScienceXTT)]], and [[hekate:hekate_bibliography#gjn2005compsci:mirella|gjn2005CompSciMirella]].
+FIXME
+mscs, regulus, kheops, ijis, ecai96, oat, dexa
+XTT (also referred to as XTT1) has been first formulated by Grzegorz J. Nalepa in [[hekate:bib:hekate_bibliography#gjn2004phd|(gjn2004phd)]], and later described in [[hekate:bib:hekate_bibliography#gjn2005sysci:xtt|(gjn2005SystemScienceXTT)]], and [[hekate:bib:hekate_bibliography#gjn2005compsci:mirella|gjn2005CompSciMirella]].
 The version described in the above papers is referred to as XTT1.
-The design was supported by the //Mirella// tool [[hekate:hekate_bibliography#gjn2005compsci:mirella|gjn2005CompSciMirella]].
+The design was supported by the //Mirella// tool [[hekate:bib:hekate_bibliography#gjn2005compsci:mirella|gjn2005CompSciMirella]].
 An important development was the supportive design method called ARD (//Attribute Relationship Diagrams//).
-It was first proposed by Antoni Ligeza in [[hekate:hekate_bibliography#ali2005thebook|(ali2005thebook)]], and later developed by Grzegorz J. Nalepa and Antoni Ligeza in [[hekate:hekate_bibliography#gjn2005:kkio]].
+It was first proposed by Antoni Ligeza in [[hekate:bib:hekate_bibliography#ali2005thebook|(ali2005thebook)]], and later developed by Grzegorz J. Nalepa and Antoni Ligęza in [[hekate:bib:hekate_bibliography#gjn2005:kkio]].
-In [[hekate:hekate_bibliography#ali2005thebook|(ali2005thebook)]] the family of //Attributive Logics// (AL) including SAL (//Set Attributive Logic//) has been described.
+In [[hekate:bib:hekate_bibliography#ali2005thebook|(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 Ligeza, for the details see:
+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:
-  * [[hekate:hekate_bibliography#|ali2007flairs-granular]]
+  * [[hekate:bib:hekate_bibliography#|ali2007flairs-granular]]
-  * [[hekate:hekate_bibliography#|gjn2007inap]]
+  * [[hekate:bib:hekate_bibliography#|gjn2007inap]]
-  * [[hekate:hekate_bibliography#|ali2007cms-xtt-extended]]
+  * [[hekate:bib:hekate_bibliography#|ali2007cms-xtt-extended]]
-  * [[hekate:hekate_bibliography#|ali2008flairs]]
+  * [[hekate:bib:hekate_bibliography#|ali2008flairs]]
 Recently some stronger formulation for the next version of XTT have been given in:
-  * [[hekate:hekate_bibliography#gjn2008ruleapps|(gjn2008ruleapps)]]
+  * [[hekate:bib:hekate_bibliography#gjn2008ruleapps|(gjn2008ruleapps)]]
-  * [[hekate:hekate_bibliography#ali2008principles|(ali2008principles)]]
+  * [[hekate:bib:hekate_bibliography#ali2008principles|(ali2008principles)]]
 At this stage XTT was referred to as XTT+.
-The name //GREP// (General Rule Programming) was also proposed in [[hekate:hekate_bibliography#gjn2007inap|]].
+The name //GREP// (General Rule Programming) was also proposed in [[hekate:bib:hekate_bibliography#gjn2007inap|gjn2007inap]].
 The proposal was an attempt to investigate the use of the XTT+ as a general programming solution.
-Originally, for XTT1 [[hekate:hekate_bibliography#gjnphd|(gjn2004phd)]] different conceptual design methods were considered.
+Originally, for XTT1 [[hekate:bib:hekate_bibliography|(gjn2004phd)]] different conceptual design methods were considered.
-The ARD method was one of the considered possibilities developed by Grzegorz J. Nalepa and Antoni Ligeza in [[hekate:hekate_bibliography#gjn2005:kkio]].
+The ARD method was one of the considered possibilities developed by Grzegorz J. Nalepa and Antoni Ligęza in [[hekate:bib:hekate_bibliography#gjn2005:kkio]].
-Later on it has been refactored and formally described by Grzegorz J. Nalepa and Igor Wojnicki in [[hekate:hekate_bibliography#gjn2007flairs-formal|(gjn2007flairs-ardformal)]].
+Later on it has been refactored and formally described by Grzegorz J. Nalepa and Igor Wojnicki in [[hekate:bib:hekate_bibliography#gjn2007flairs-formal|(gjn2007flairs-ardformal)]].
 This current version is called //ARD+//.
@@ Line 55: / Line 66: @@
 However, in the future the ARD+ shall be replaced by more advanced methods.
-Basing 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 Ligeza in 2008.
+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.
 ===== Formal Rules Description =====
-The rules in XTT^2 are //formally/ described in an //attributive language//.
+The rules in XTT^2 are //formally// described in an //attributive language//.
 The underlying logic is //[[hekate:alsvfd|Attributive Logic with Set Values over Finite Domains]]//, or ALSV(FD) for short.
@@ Line 89: / Line 100: @@
 ==== XTT Constraints ====
-Rule prototypes these hint for XTT tables:
+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 FIXME this requires some research
+  * relations (inference order) -> [[hekate:xtt2#links|default links (table2table)]] can be inferred
 (Please discuss at the [[hekatedev:xtt2#XTT constraints]] page.)
 ==== Communication Constraints ====
-To some extent tey should also point to attribute communication classes.
+To some extent they should also point to attribute communication classes.
-By default we should assume that:
+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 no other dependent on, are //output// ones,
-  * attributes that are and have dependants are //internal//
+  * attributes that are and have dependants are //internal// ones.
 ===== XTT Rules =====
-On a general level, an XTT rule is a [[wp>Rule of Inference]].
+On a general level, an XTT rule is a [[wp>Rule of Inference]] or, more precisely, a //production rule// i.e. a basic component of any [[http://en.wikipedia.org/wiki/Production_system|Production Rule System]].
 It is composed of the:
-  * //LHS// (Left Hand Side), that is a set of premises, condition, and
+  * //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.
+  * //RHS// (Right Hand Side)), that is the decision, conclusion, hypothesis or action.
 ==== Rule Prototype ====
@@ Line 120: / Line 131: @@
 The XTT rule LHS is a //tuple of ALSV formulas//, as described in detail in [[hekate:alsvfd#syntax]].
-Logically, the LHS a corresponds to a //conjuction// of premises as in the classic inference rule definition.
+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:
@@ Line 131: / Line 142: @@
 ==== Rule Firing ====
-The current values of all the attributes are specified with the contents of the knowledge-base.
+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:
@@ Line 155: / Line 166: @@
 See [[hekate:xtt2#Inference]] for more details.
 ==== Rule RHS ====
@@ Line 165: / Line 175: @@
 The rule RHS can contain:
-  * state changes, that is attribute values modifications
+  * state changes, that is attribute values modifications (with use of retract/assert, FIXME 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 system 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
+  * link that specifies inference control (e.g. a switch/case or a loop),
+++++Some consequences - backtracking|
+no parameter passing,
+no backtracking,
+simple solution
+++++
 === Attribute value modification ===
@@ Line 187: / Line 203: @@
-.2) Algebraic expressions in case of numeric attributes only; the expression can contain numbers, predefined algebraic operators and functions, as well as attribute values (Prolog //is//).
+.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//).
 ) External action specification;
@@ Line 218: / Line 234: @@
 A table provides a //visual// representation of rules, as below.
-{{xttp-table-new.png|XTT table new format}}
+{{xttp-table-new.png|XTT table new format}} FIXME
 Rules in the table are interpreted one by one in a given way (see [[hekate:xtt2#Inference]]), this is the Table Inference.
@@ Line 224: / Line 240: @@
 Table rows (rules) may be connected to other tables (rows) by links.
 This forms a tree-like structure.
-This is the Tree Inference.
+This is the Tree-like Inference.
+(//In fact, it is more close to a **graph** representing a partial order of inference//).
 ==== Table Scheme ====
@@ Line 240: / Line 257: @@
 In the future more types could be identified.
 (Please discuss at the [[hekatedev:xtt2#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.
 ===== Inference =====
@@ Line 269: / Line 292: @@
 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).
+FIXME
+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.
@@ Line 275: / Line 307: @@
 XTT tables are connected with //links//.
-A link representes a inference control mechanism.
+A link represents a inference control mechanism.
 It also be thought of as a
 dependency mechanism,
@@ Line 282: / Line 314: @@
 partial order.
-In general we consider //positive links//, that  is links that are followed where a rule is fired.
 Links are deterministic, that is a single rule decision can have a //single// link only.
-FIXME ALi
+In general we consider //positive links//, that  is links that are followed where a rule is fired.
-It should be decided whether we consider explicit negative (else) links, possibly at the table2table level.
+The designer can introduce //explicit negative links// by
+using an explicitly defined positive construction of the following scheme:
+<code>
+precondtions --> conclusion| next(table.rule)
+true         -->           | else(table.rule)
+</code>
+FIXME
+We can consider introducing number of global meta-interference attributes,
+such as "mode_of_operation", "task", "did_any_rule_in_table_fired", etc.
 === Links ===
 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 a nother table
+  * //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.
-  * //table-table// (t2t) the link is established at the table level, meaning when all rules in the table fire the control is transfered to another table. This is a case, where a negative t2t link could be considered.
+FIXME: 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.
+++++More on intertable links|
+In general, we should have inter-tables links and inside-table links.
+Both of them can be defined with TableOut.RuleOut --> TableIN.RuleIN model.
+However, for the inside table links we can define simple policies, such as a top-bottom order, top-first-fired order, without without circular interpretation.
+++++
 === Link implementation ===
   - 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 additiona representation to the first one.
+  - 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/atble depend by backward chaining.
+Using the 2nd solution it would be easy to find all tables/rules on which a given rule/table depend by backward chaining.
 === Branching ===
@@ Line 305: / Line 354: @@
 Problem: In a general case, there might be multiple entry points in the XTT structure.
-Consider a tree (Ts are XTT tables) structure like this:
+(See the discussion at the [[hekatedev:xtt2#Branching]] page.)
-  T1-
-      > T5 -
-  T2-        \
-              T7
-  T3-        /
-      > T6 -
-  T4-
-A //fired table// is a table allready interpreted by the engine.
-To handle this we might introduce a simple backward-chaining approach.
-  * build a list of tables that can be fired
-  * fire any table with no preceeding table, no incoming links or mark a selected table as a start table,
-  * follow links to fire subsequent tables
-  * to fire a table, no attributes in the condition can have the //NOT_DEFINED// value, in case of such a table backtrack to another table preeceeding this one
-  * another solution, suitable for a single pass interpreter is to keep track of fired tables.
-Another approach would be to predeterine the sets of tables can be fired at the beginning of the inference by a backward-chainig analysis of table schemes (ARD prototypes).
-The above problem seem to apply only to the initional inference, not to a general brachnig structure like this:
-       Tj
-     /    \
-  Ti       Tl
-     \   /
-       Tk
-In this case the inference is deterministic, and depends on which rules in the first table Ti are fired.
-FIXME ALi
+//A temporary semi-parallel solution//:
+ARD introduces partial order in tables,
+tables can be fired in any way,
+as long as this contstraint holds.
-(Please discuss at the [[hekatedev:xtt2#Branching]] page.)
+FIXME: 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.
 ==== Interpreter Scenarios ====
@@ Line 351: / Line 379: @@
   * 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 differnet approaches to C
+  * 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
@@ Line 367: / Line 395: @@
 The //Single Pass// interpreter is the simplest scenario:
-  - the interpreter is executed externaly by the user, system, etc.
+  - the interpreter is executed externally by the user, system, etc.
   - input attribute callbacks provide input facts
   - the inference starts
@@ Line 376: / Line 404: @@
 For sanity, it should be assumed, that no attributes input/communication attributes are updated during the inference.
+FIXME 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.
@@ Line 385: / Line 415: @@
 ==== State Modeling ====
-The following assumptions for system modelling with ALSV rules is given:
+The following assumptions for system modeling with ALSV rules is given:
-  * the system is modelled with the use of attributes (state variables!),
+  * 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,
@@ Line 405: / Line 435: @@
 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 nvironment).
+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.
@@ Line 418: / Line 448: @@
   * input (S <- E),
   * output (S ->  E),
-  * internal (S -> S), (was ``middle'' in XTTv1)
+  * internal (S -> S), (was ''middle'' in XTTv1)
   * communication (comm) (S <-> E)
 Arrows indicate the System/Environment interaction.
+FIXME: iw: what's happened to ''ro, rw, wo, state'' classes?
 Discuss ideas here: [[hekatedev:xtt2#Attribute Classes]].
@@ Line 433: / Line 465: @@
 ===== HeKatE Meta Representation =====
-FIXME ALi
 The following textual algebraic representation is provided.
@@ Line 452: / Line 482: @@
 Fact:
-FIXME ALi
 ===== XTT Analysis =====
@@ Line 462: / Line 492: @@
 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.
 ===== XTT^2 Markup =====
@@ Line 489: / Line 526: @@
 ==== Possible ====
+=== Inference with backtracking and cut===
 === Hierarchical types ===
@@ Line 499: / Line 538: @@
 This could be possibly cobmined with the so-called //scope// from the XTT+.
+=== Link labeling ===
+If it is of ANY use?
 ==== Deprecated ====
@@ Line 515: / Line 556: @@
 declarative  inference control spec
+FIXME
+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).

hekate/xtt2.1226962126.txt.gz · Last modified: 2019/06/27 16:00 (external edit)

Show page Old revisions

Media Manager Back to top

AIwiki

Menu

Dla Studentów

Old specialized AI courses

SMaDA/SMaIDA/AIDA

Informatyka (EAIiIB)

Studia Dr

Inne materialy dydaktyczne

Archiwum

Dyplomanci

Geist Season of Code

HeKatE

Public

HeKatE

Differences