Grammar Specs

Revision as of 16:42, 17 March 2011

UNL-NL grammars are sets of rules for translating UNL expressions into natural language (NL) sentences and NL sentences into UNL expressions. They are normally unidirectional, i.e., the enconversion grammar (NL-to-UNL) is different from the deconversion grammar (UNL-to-NL), even though they share the same basic syntax. In order to standardize the language resources in the UNL framework, the UNDL Foundation recommends the adoption of the following specifications for both UNL-to-NL and NL-to-UNL grammars. This formalism, however, is not supported by the UNL Centre's tools, and it is only required by those interested in using UNDL Foundation's tools.

Types of rules

In the UNL Grammar there are two basic types of rules:

Transformation rules

Used to generate natural language sentences out of UNL graphs and vice-versa.

Disambiguation rules

Used to improve the performance of transformation rules by constraining their applicability.

The Transformation Rules follow the very general formalism

α:=β;

where the left side α is a condition statement, and the right side β is an action to be performed over α.

The Disambiguation Rules, which were directly inspired by the UNL Centre's former co-occurrence dictionary and knowledge base, follows a slightly different formalism:

α=P;

where the left side α is a statement and the right side P is an integer from 0 to 255 that indicates the probability of occurrence of α.

We present both types of rules and their role in the UNL System. We introduce, first, the basic symbols that are used both by transformation and disambiguation rules; next, we present the transformation rules and their several subtypes; and finally we present the disambiguation rules.

Node

Transformation and disambiguation rules apply over nodes, either in a natural language sentence structure or in the UNL hypergraph structure. The node is the basic unit in the grammar and may be referred by:

• a string, to be expressed between "quotes";
• a dictionary entry, to be expressed between [square brackets];
• a dictionary sub-entry
• a feature (attribute, value, or attribute-value pair) or set of features of a dictionary entry;
• a pointer (index) to an existing node; and
• a relation between nodes (i.e., a hypernode).

Nodes can also be a combination of such values. Examples of nodes are

• "ing" (string)
• [book] (entry)
• [[book(icl>document)]] (UW)
• NUM (feature)
• NOU (value)
• VA(01>02) (value)
• POS=NOU (attribute-value pair)
• %01 (pointer)
• %01%01%01 (pointer)
• %source (pointer)
• %01#01 (pointer to a dictionary sub-entry)
• agt(VER;NOU) (relation)
• PP(PB(PC(PRE;NP);PP);DP) (relation)
• [book],POS=NOU,%01 (combination of several possibilities)

Basic symbols

Both transformation and disambiguation rules use the same set of basic symbols to address nodes:

The differences between "", [] and [[]]

Double quotes are always used to represent strings: "a" will match only the string "a"

Simple square brackets are always used to represent natural language entries (headwords) in the dictionary: [a] will match the node associated to the entry [a] retrieved from the dictionary, no matter its current realization, which may be affected by other rules (the original [a] may have been replaced, for instance, by "b", but will still be indexed to the entry [a])

Double square brackets are always used to represent UWs: [[a]] will match the node associated to the UW [[a]]

Predefined values (assigned by default)

SCOPE - Scope

SHEAD - Sentence head (the first node in a sentence)

STAIL - Sentence tail (the last node in a sentence)

CHEAD - Scope head (the first node in a scope)

CTAIL - Scope tail (the last node in a scope)

TEMP - Temporary entry (entry not found in the dictionary)

ANUM - Any sequence of Arabic numerals (i.e.: 0,1,2,3,4,5,6,7,8,9)

Transformation rules

Natural language sentences and UNL graphs are supposed to convey the same amount of information in different structures: whereas the former arranges data as an ordered list of words, the latter organizes it as a hypergraph. In that sense, translating from natural language into UNL and from UNL into natural language is ultimately a matter of transforming lists into networks and vice-versa.

The UNDLF generation and analysis tools assume that such transformation should be carried out progressively, i.e., through a transitional data structure: the tree, which could be used as an interface between lists and networks. Accordingly, the UNL Grammar states seven different types of rules (LL, TT, NN, LT, TL, TN, NT), as indicated below:

• ANALYSIS (NL-UNL)
  • LL - List Processing (list-to-list)
  • LT - Surface-Structure Formation (list-to-tree)
  • TT - Syntactic Processing (tree-to-tree)
  • TN - Deep-Structure Formation (tree-to-network)
  • NN - Semantic Processing (network-to-network)

• GENERATION (UNL-NL)
  • NN - Semantic Processing (network-to-network)
  • NT - Deep-Structure Formation (network-to-tree)
  • TT - Syntactic Processing (tree-to-tree)
  • TL - Surface-Structure Formation (tree-to-list)
  • LL - List Processing (list-to-list)

The NL original sentence is supposed to be preprocessed, by the LL rules, in order to become an ordered list. Next, the resulting list structure is parsed with the LT rules, so as to unveil its surface syntactic structure, which is already a tree. The tree structure is further processed by the TT rules in order to expose its inner organization, the deep syntactic structure, which is supposed to be more suitable to the semantic interpretation. Then, this deep syntactic structure is projected into a semantic network by the TN rules. The resultant semantic network is then post-edited by the NN rules in order to comply with UNL standards and generate the UNL Graph.

The reverse process is carried out during natural language generation. The UNL graph is preprocessed by the NN rules in order to become a more easily tractable semantic network. The resulting network structure is converted, by the NT rules, into a syntactic structure, which is still distant from the surface structure, as it is directly derived from the semantic arrangement. This deep syntactic structure is subsequently transformed into a surface syntactic structure by the TT rules. The surface syntactic structure undergoes many other changes according to the TL rules, which generate a NL-like list structure. This list structure is finally realized as a natural language sentence by the LL rules.

As sentences are complex structures that may contain nested or embedded phrases, both the analysis and the generation processes may be interleaved rather than pipelined. This means that the natural flow described above is only "normal" and not "necessary". During natural language generation, a LL rule may apply prior to a TT rule, or a NN rule may be applied after a TL rule. Rules are recursive and must be applied in the order defined in the grammar as long as their conditions are true, regardless of the state.

Network-to-Network Rules

The network-to-network rules (NN) are used for processing networks, both in analysis and in generation. During analysis, these rules are used for post-editing the semantic network structure derived from the syntactic module in order to generate the UNL graph; in generation, they are used for pre-editing the UNL graph, transforming it into a semantic network that would be more appropriate for sentence generation.

There are 4 different subtypes of NN rules:

Tree-to-Tree Rules

The tree-to-tree rules (TT) are used for processing trees, both in analysis and in generation. During analysis, these rules are used for revealing the deep structure out of the surface structure; in generation, they are used for transforming the deep into the surface syntactic structure.

Syntactic relations are n-ary: they can have as many arguments (nodes) as necessary.

There are 5 different subtypes of TT rules:

As syntactic relations are n-ary, the REPLACE RELATION may also be used to ADD or DELETE nodes.

List-to-List Rules

The list-to-list (LL) rules are used for processing lists, both in analysis and in generation. In analysis, these rules are used for pre-editing the natural language sentence and preparing the input to the syntactic module; in generation, they are used for post-editing the output of the syntactic module and generating the natural language sentence.

There are 5 different subtypes of LL rules:

List-to-Tree Rules

The list-to-tree (LT) rules are used to parse the list structure into a (surface) tree structure. It is used only in analysis, and all LT rules follow the syntax below:

Tree-to-List Rules

The tree-to-list (TL) rules are used to linearize the (surface) tree structure into a list structure. It is used only in generation, and all TL rules follow the syntax below:

There is a single type of TL rule:

Tree-to-Network Rules

The tree-to-network (TN) rules derive a semantic network out of a syntactic tree. It is used only in analysis, and all TN rules follow the syntax below:

There is a single type of TN rule:

Network-to-Tree Rules

The network-to-tree (NT) rules reorganizes the network structure as a deep tree structure. It is used only in generation.

There is a single type of TN rule:

Formal Syntax of Transformation Rules

<TRANSFORMATION RULE> ::= <NN RULE> | <NT RULE> | <TT RULE> | <TL RULE> | <LL RULE> | <LT RULE> | <TN RULE>
<NN RULE>             ::= (<SEM>)+ ":=" ( ("-"|"+")? <SEM> )* ";"
<TT RULE>             ::= (<SYN>)+ ":=" ( ("-"|"+")? <SYN> )* ";"
<LL RULE>             ::= ( "(" <NODE> ")" )+ ":=" ( ("-"|"+")? "(" <NODE> ")" )* ";"
<NT RULE>             ::= (<SEM>)+ ":=" ( <SYN> )+ ";"
<TN RULE>             ::= (<SYN>)+ ":=" ( <SEM> )+ ";"
<TL RULE>             ::= (<SYN>)+ ":=" ( "(" <NODE> ")" )+ ";"
<LT RULE>             ::= ( "(" <NODE> ")" )+ ":=" ( <SYN> )+ ";"
<SEM>                 ::= <TEXT> "(" <NODE> ";" <NODE> ")"
<SYN>                 ::= <TEXT> "(" <NODE> ";" <NODE> ")"
<NODE>                ::= ( (<DESCRIPTION>)( "," <DESCRIPTION> )* )?
<DESCRIPTION>         ::= <STRING> | <ENTRY> | <SUB-ENTRY> | <FEATURE> | <INDEX> | <RELATION>
<STRING>              ::= """<text>"""
<ENTRY>               ::= "["<entry>"]"
<SUB-ENTRY>           ::= <INDEX>"#"[01-99]
<FEATURE>             ::= <VALUE> | <ATTRIBUTE> | <ATTRIBUTE>"="<VALUE>
<INDEX>               ::= ( "%"([01-99]|[a-zA-Z_]+) )+
<RELATION>            ::= <SEM>|<SYN>
<VALUE>               ::= <TEXT>
<ATTRIBUTE>           ::= <TEXT>
<TEXT>                ::= any sequence of characters except whitespace | <REGULAR EXPRESSION>
<REGULAR EXPRESSION>  ::= "/"<PERL COMPATIBLE REGULAR EXPRESSIONS>"/"

Where:
"" = constant
+ = to be repeated one or more times
* = to be repeated zero or more times
? = to be repeated zero or one time
| = or
[x-y] = from x to y

Disambiguation Rules

Apart from Transformation Rules, the UNL Grammar also comprises Disambiguation Rules, which are optional and may be used to:

• Prevent wrong lexical choices;
• Provoke best matches;
• Check the consistency of the graphs, trees and lists.

The formalism here presented is directly inspired by UNL Centre former co-occurrence dictionary and knowledge-base. The structure of the rule is as follows:

STATEMENT=P;

Where
STATEMENT is any network, tree or list relation; and
P, which can range from 0 (impossible) to 255 (possible), is the probability of occurrence of the STATEMENT

There are three types of disambiguation rules:

• Network disambiguation rules
• Tree disambiguation rules
• List disambiguation rules

Network Disambiguation Rules

Network disambiguation rules apply over the network structure of UNL graphs to constrain the application of Tree-to-Network (TN) and Network-to-Network (NN) Transformation Rules. They have the following format:

SEM(A;B)=P;

Where SEM is a semantic relation, A and B are nodes, and P is an integer (from 0 to 255).

Examples

agt(VER;ADJ)=0;

An adjective (ADJ) may not be an agent (agt) of a verb (VER).

agt(VER;NOU)=255;

Agents (agt) of verbs (VER) are always nouns (NOU).

Use

Tree Disambiguation Rules

Tree disambiguation rules apply over the intermediate tree structure to constrain the application of List-to-Tree (LT), Network-to-Tree (NT) and Tree-to-Tree (TT) Transformation Rules. They have the following format:

SYN(A;B)=P;

Where SYN is a syntactic relation, A and B are nodes, and P is an integer (from 0 to 255).

Examples

VS(VER;ADJ)=0;

An adjective (ADJ) may not be an specifier (VS) of a verb (VER).

NS(NOU;DET)=255;

Determiners (DET) are always specifiers (NS) of nouns (NOU).

Use

List Disambiguation Rules

List disambiguation rules apply over the natural language list structure to constrain the application of both Tree-to-List (TL) and List-to-List (LL) Transformation Rules. They are also used for word selection. They have the following format:

(A)(B)=P;

Where A and B are nodes, and P is an integer (from 0 to 255).

Examples

(ART)(BLK)(VER)=0;

An article (ART) may not precede a verb (VER).

(ART)(BLK)(NOU)=255;

Articles (ART) always precede nouns (NOU).

Use

Formal Syntax of Disambiguation Rules

Disambiguation rules must comply with the following syntax

<DISAMBIGUATION RULE> ::= <NN RULE> | <TT RULE> | <LL RULE> 
<NN RULE>             ::= (<SEM>)+ "=" [0-255]";"
<TT RULE>             ::= (<SYN>)+ "=" [0-255]";"
<LL RULE>             ::= "(" <NODE> ")" ( "(" <NODE> ")" )+ "=" [0-255]";"
<SEM>                 ::= <TEXT> "(" <NODE> ";" <NODE> ")"
<SYN>                 ::= <TEXT> "(" <NODE> ";" <NODE> ")"
<NODE>                ::= ( (<DESCRIPTION>)( "," <DESCRIPTION> )* )?
<DESCRIPTION>         ::= <STRING> | <ENTRY> | <FEATURE> | <RELATION>
<STRING>              ::= """<text>"""
<ENTRY>               ::= "["<entry>"]"
<FEATURE>             ::= <VALUE> | <ATTRIBUTE> | <ATTRIBUTE>"="<VALUE>
<RELATION>            ::= <SEM>|<SYN>
<VALUE>               ::= <TEXT>
<ATTRIBUTE>           ::= <TEXT>
<TEXT>                ::= any sequence of characters except whitespace | <REGULAR EXPRESSION>
<REGULAR EXPRESSION>  ::= "/"<PERL COMPATIBLE REGULAR EXPRESSIONS>"/"

General Properties of Grammar Rules

PRIORITY

Rules should be applied serially, according to the order defined in the grammar. The first rule will be the first to be applied, the second will the second, and so on.

RECURSIVENESS

Rules should be applied recursively as long as their conditions are true.

COMPREHENSIVENESS

Grammars should be applied comprehensively as long as there is at least one applicable rule.

ACTION

The rules may add or delete values to the source and the target nodes, but only in the right side items:

agt(a;b):=agt(+c;);

agt(a;b):=agt(;-b);

CONSERVATION

Rules affect only the information clearly specified. No relation, node or feature is deleted unless explicitly informed.

For instance, in the examples below, the source node of the “agt” relation preserves, in all cases, the value “a”. The only change concerns the feature “c”, which is added to the source node of the “agt” in the first two cases; and the feature “b”, which is deleted from the target node in the third case.

agt(a;b):=agt(c;);

agt(a;b):=agt(+c;);

agt(a;b):=agt(;-b);

In any case, the ADD and DELETE rules (i.e., when the right side starts with “+”or “-“) preserve the items in the left side, except for the explicitly deleted ones:

INPUT: agt(a;b) obj(a;c) tim(a;d)

RULE: agt(a;b) ^mod(a;e):=+mod(a;e);

OUTPUT: agt(a;b) obj(a;c), tim(a;d), mod(a;e)

or

INPUT: agt(a;b) obj(a;c) tim(a;d)

RULE: agt(a;b):=-agt(a;b);

OUTPUT: obj(a;c) tim(a;d)

The REPLACE, MERGE and DIVIDE rules affect only their designated scopes. In that sense, NN may only replace, merge or divide semantic relations; TT may only replace, merge or divide syntactic relations; and LL may only replace, merge or divide list nodes. All other information is preserved, unless explicitly informed.

INPUT: agt(a;b) cob(a;c)

RULE: cob(;):=obj(;);

OUTPUT: agt(a;b) obj(a;c)

or

INPUT: agt(a;b) cob(a;c)

RULE: cob(a;):=obj(-a,+d;);

OUTPUT: agt(a;b) obj(d;c)

CONJUNCTION

Both the left and the right side of the rule may have as many items as necessary, as exemplified below:

SEM(A;B)SEM(C;D)SEM(E;F):=SEM(G;H)SEM(I;J)SEM(K;L);

DISJUNCTION

The left side of the rules may bring disjuncts, but not the right side. Disjuncts must be represented between {braces} and alternative must be separated by |.

{SEM(A;B)|SEM(C;D)}^SEM(E;F):=+SEM(E;F);

SEM(A;B){SEM(C;D)|SEM(E;F)}:=-SEM(A;B);

agt(VER,{V01|V02};NOU,^SNG}:=;

EXTENDIBILITY

The left side of the rules may bring [Perl Compatible Regular Expressions] between "/", as indicated below:

/(agt|obj|aoj)/(A,%a;B,%b):=VS(%a;%b);

The rule above applies in case of agt(A;B), obj(A;B) and aoj(A;B)

/[a-z]{2,3}/(A,%a;B,%b):=VS(%a;%b);

The rule above applies in case of any sequence of two or three alphabetic characters in the position of relation of A and B

agt(/(VER|NOU)/,%a;%b):=VS(%a;%b);

The rule above applies in case of VER and NOU as features of the first node of the relation "agt"

agt(POS=/(VER|NOU)/,%a;%b):=VS(%a;%b);

The rule above applies in case of VER and NOU as values of the attribute POS of the first node of the relation "agt"

CONCISION

Rules should be as small as possible. In that sense, the source and the target nodes may be simple place-holders or indexes:

cob(;):=obj(;);

tim(%01;[[in]]),obj([[in]];%02):=tim(%01;%02);

tim(VER,%01;[[in]]),obj([[in]];NOU,%02):=tim(%01;%02);

tim(VER;in),obj(in;NOU):=tim(;%04);

In the DELETE rules, the right side may be omitted in case of deletion of the entire left side:

obj(PRE;):=;

READABILITY

There can be blank spaces between variables and symbols. Comments can be added after the “;”.

obj ( ; ) := ; this rule deletes every “obj” relation.

SCOPE GENERATION

Inside a relation, nodes can be relations (i.e., hypernodes).

SEM(A;SEM(C;D)):=SEM(A;C),SEM(C;D));

SEM(A;C),SEM(C;D):=SEM(A;SEM(C;D));

COMMUTATIVITY

Inside the same side of NN, NT, TT and TN rules, the order of the factors does not affect the result^[1]

SEM(A;B):=SEM(C;D)SEM(E;F); IS EQUIVALENT TO SEM(A;B):= SEM(E;F)SEM(C;D);

SYN(A;B):=SYN(C;D)SYN(E;F); IS EQUIVALENT TO SYN(A;B):= SYN(E;F)SYN(C;D);

The order of the factors affect the result in case list-processing rules (LL, LT and TL):

(A):=(B)(C); IS DIFFERENT FROM (A):=(C)(B);

SYN(A;B):=(C)(D); IS DIFFERENT FROM SYN(A;B):=(D)(C);

(C)(D):=SYN(A;B); IS DIFFERENT FROM (D)(C):=SYN(A;B);

Additionally, the order of the features inside a relation does not affect the end result, but the order of the nodes is non-commutative.

SEM( VER,TRA ; NOU,MCL ) IS THE SAME AS SEM( TRA,VER ; MCL,NOU )

But:

SEM( VER,TRA ; NOU,MCL) IS DIFFERENT FROM SEM( NOU,MCL ; VER,TRA )

DICTIONARY ATTRIBUTES

Dictionary attributes can be used as variables (see indexes).

SYN( A,^num ; B,num ):=SYN( A,num=%02; %02 );

DICTIONARY RULES (see also Inflection rules inside dictionary entries)

Dictionary rules are triggered by "!"<ATTRIBUTE>:

Dictionary

[foot] "foot" (NOU, NUM(PLR:=”oo”:”ee”)) <eng,0,0>;

[city] "city" (NOU, NUM(PLR:=”y”>”ies”)) <eng,0,0>;

Grammar

(@pl, NUM):=(!NUM,-@pl);

Output

foot>feet

city>cities

NLW SPLITTING

Sub-NLWs in complex entries are referred by # (see indexes).

Dictionary

[[bring] [back]] "bring back" (VER,MTW,VA(01>02), #01(HEAD,VER), #02(ADJT,PP)) <eng,0,0>;

Grammar

VC(VER,MTW,VA(01>02),%head;NOU,%obj):=VB(VC(%head#01;%obj);%head#02);

Indexes

Indexes (%) are used for co-indexing nodes, attributes and values inside and between the left and the right side of transformation rules.

X(%a;)Y(%a;) (the first node of X is also the first node of Y)

X(%a;%b):=Y(%b;%a); (the first node of X becomes the second node of Y, and the second node of X becomes the first node of Y)

X(%a;)Y(%a;):=Z(%a); (if the first node of X is the first node of Y then make it the single node of Z)

Any co-indexation is made by the use of indexes and not by the repetition of features. In that sense, X(A;)Y(A;) is different from X(%a;)Y(%a;). In the former case, the first node of X is not necessarily the first node of Y, they only share the same feature A; in the latter case, the first node of X is necessarily the first node of Y.

Indexes are made of any sequence of alphanumeric characters and underscore

%index

%a

%first_index

%a1

%first index (no blank spaces are allowed)

%01 (numbers are used for default indexation and must be avoided - see below)

Default indexation

If omitted, indexes are assigned by default, according to the following rules:

Default indexes are assigned from left to right in each side of the rule according to the position:

X(A;B)Y(C;D) is the same as X(%01,A;%02,B)Y(%03,C;%04,D)

Default indexation is done only for non-indexed nodes:

X(A,%A;B)Y(C,%C;D) is the same as X(A,%A;B,%02)Y(C,%C;%04,D)

(Notice that the user-defined indexes %A and %C are preserved and not replaced by default indexes)

In default indexation, left-side nodes are automatically co-indexed with right-side nodes if and only if their position and number are the same:

X(A;B):=Y(C;D); is the same as X(%01,A;%02,B):=Y(%01,C;%02,D);

X(A;B):=Y(C;D;E); is the same as X(%01,A;%02,B):=Y(%03,C;%04,D;%05,E);

(there is no co-indexation between the left and the right side in the latter case, because the number of the nodes is not the same)

In default indexation, sub-nodes are informed by the syntax <PARENT NODE><CHILD NODE>, where <PARENT NODE> may be, itself, a sub-node:

X(Y(A;B);C) is the same as X(%01,Y(%01%01,A;%01%02,B);%02)

%01 = Y(A;B), %02 = C, %01%01 = A, %01%02 = B

X(Y(Z(A;B);C);D) is the same as X(%01,Y(%01%01,Z(%01%01%01,A;%01%01%02,B);%01%02,C);%02,D)

%01 = Y(Z(A;B);C), %02 = D, %01%01 = Z(A;B), %01%02 = C, %01%01%01 = A, %01%01%02 = B

Non-indexed nodes in the right side means ADDITION, whereas left-side nodes that are not referred to in the right side means DELETION

X(%a;%b):=Y(%a;X;%b); is the same as X(%a;%b):=Y(%a;%02,X,;%b); (it means that a new node with the feature X will be created for the relation Y)

X(%a;%b;%c):=Y(%a;%c); (it means that the second node of X will be deleted from the relation Y)

Indexes may also be used to transfer attribute values expressed in the format ATTRIBUTE=VALUE

X(A,%a,ATT1=VAL1;B,%b):=X(%a;%b,ATT1=%a); (the value "VAL1" of "ATT1" of %a is copied to the node %b)

Special indexes (#) are used to make reference to the internal structure of the field <NLW> in the dictionary

(X)(Y):=(X,#02)(Y)(X,#01);

The rule above is used for complex dictionary entries such as:

[[A][B]] "uw" (X, #01(ATT=AAA), #02(ATT=BBB)) <flg,fre,pri>;

It means that, given (X)(Y), the output should be (B)(Y)(A).

Example of Rules

INITIAL STATE: L(%A;%B) L(%B;%C) L(%C;%D) L:B(%B1;%B2) L:B(%B2;%B3) REL:B(%B1;%B4) Where:
L(A;B) is a linear (list) relation between A and B (i.e., L(A;B) = (A)(B))
%X is the index for a node

X indicates that the relation or a node is inside a hyper-node

In the examples below, A,B,C,D,B1,B2,B3 and B4 are features of the nodes %A,%B,%C,%D,%B1,%B2,%B3 and %B4, respectively.

RULE#1: (B)

=;

(Delete the nodes with the feature B)

FINAL STATE: L(%A;%C) L(%C;%D)

The whole hyper-node %B will be deleted, including all its nodes, no matter in which level.

RULE#2: (B1)

=;

(Delete the nodes with the feature B1)

FINAL STATE: L(%A;%B) L(%B;%C) L(%C;%D) L:B(%B2;%B3) :B(%B4)

Only the node (%B1) is deleted. The relation REL is also deleted, but the node %B4 is preserved as an isolated node inside the hyper-node %B.

RULE#3: ((B1))

=;

(Delete the hyper-node that contains the node with the feature B1);

FINAL STATE: L(%A;%C) L(%C;%D)

The whole hyper-node %B will be deleted, including all its nodes, no matter in which level.

RULE#4: (B1)

=(NEW);

(Add the feature “NEW” to the nodes containing the feature B1)

FINAL STATE: L(%A;%B) L(%B;%C) L(%C;%D) L:B(%B1;%B2) L:B(%B2;%B3) REL:B(%B1;%B4) (NO CHANGE IN THE NODE STRUCTURE)

There is no indexes in the left and the right side, which have the same number of nodes. This means that they are automatically co-indexed. No node is deleted or replaced. The feature “NEW” is added to the the node %B1, because it contains the feature B1.

RULE#5: (%x,B1)

=(%y,NEW);

(Replace the node containing the feature B1 by a new node containing the feature NEW)

FINAL STATE: L(%A;%B) L(%B;%C) L(%C;%D) L:B(%NEW;%B2) L:B(%B2;%B3) REL:B(%NEW;%B4)

The node %B1 is deleted and replaced by a new node %NEW. Notice that all instances of the node are replaced.

RULE#6: ((B1),(B3))

=;

(Delete the node that contains the nodes that have the features B1 and B3);

FINAL STATE: L(%A;%C) L(%C;%D)

The whole hyper-node %B will be deleted, including all its nodes, no matter in which level.

RULE#7: ((B1)(B2))

=;

(Delete the node that contains the relation L(B1;B2));

FINAL STATE: L(%A;%C) L(%C;%D)

The whole hyper-node %B will be deleted, including all its nodes, no matter in which level.

RULE#8: ((B1)(B3))

=;

(Delete the node that contains the relation L(B1;B3))

Nothing happens. The condition is not true in this case.

RULE#9: ((B1))

=(-feature);

(Remove the feature “feature” from the hyper-node containing a node with the feature B1)

As the left and the right side do not have indexes, they are automatically co-indexed. The co-indexation, however, is valid only to the hyper-node level, because the right side does not contain any inner node. In that sense, the feature “feature” is not removed from the inner node, but from the hyper-node.

RULE#10: ((B1)):=((-feature));

(Remove the feature “feature” from the node containing the feature B1 and which is inside a hyper-node)

The automatic indexation affects both levels: the hyper-node and the node, because they are equivalent. The rule is the same as (%x(%y,B1)):=(%x(%y,-feature));. The feature “feature” is now removed from the inner node and not from the hyper-node.

RULE#11: ((%x,B1)):=((%y,NEW));

(Replace the node containing the feature B1 inside the hyper-node by a new node containing the feature B5)

FINAL STATE: L(%A;%B) L(%B;%C) L(%C;%D) L:B(%HB;%B2) L:B(%B2;%B3) REL:B(%HB;%B4) L:HB(%E;%F)

RULE#12: ((B1)):=((E)(F));

(Replace the node containing the feature B1 by a linear relation between two new nodes containing the features E and F, respectively)

FINAL STATE: L(%A;%B) L(%B;%C) L(%C;%D) L:B(%HB;%B2) L:B(%B2;%B3) REL:B(%HB;%B4) L:HB(E;F)

The automatic indexation affects only the hyper-node level, because the number of arguments is different inside the hyper-node. The rule is the same as (%x(%y,B1)):=(%x(%y,E)(%z,F)). (E)(F) constitute a linear relation.

RULE#13: ((B1)):=((E),(F));

(Replace the node containing the feature B1 by two new nodes containing the features E and F, respectively)

dd two new nodes containing the features E and F, respectively, to the hyper-node containing the node with the feature B1)

FINAL STATE: L(%A;%B) L(%B;%C) L(%C;%D) L:B(%HB;%B2) L:B(%B2;%B3) REL:B(%HB;%B4) :HB(E) :HB(F)

The nodes (E) and (F) no longer constitute a linear relation, and are added as isolated notes to the hyper-node.

RULE#14: (%B1)(%B2):=REL(%B1;%B2);

(Replace the relation L(%B1;%B2) with the relation REL(%B1;%B2))

FINAL STATE: L(%A;%B) L(%B;%C) L(%C;%D) REL:B(%B1;%B2) L:B(%B2;%B3) REL:B(%B1;%B4)

No node is deleted, but there’s no longer a linear relation between %B1 and %B2. There’s still, however, a linear relation between %B2 and %B3 inside the hyper-node %B.

RULE#15: (%B1)(%B2)(%B3):=REL(%B1;%B2);

(Replace the relations L(%B1;%B2)L(%B2;%B3) with the relation REL(%B1;%B2))

FINAL STATE: L(%A;%B) L(%B;%C) L(%C;%D) REL:B(%B1;%B2) B:(%B3) REL:B(%B1;%B4)

No node is deleted (because no node may be deleted through LT rules), but the node %B3 is now isolated inside the hyper-node %B.

RULE#16: (%B1)(%B3)(%B2):=REL(%B1;%B2);

(Replace the relations L(%B1;%B3)L(%B3;%B2) with the relation REL(%B1;%B2))

Nothing happens. The condition is not true in this case.

RULE#17:

(%B1):=REL(%B1;%B4); (Replace the node %B1 by the relation REL(%B1;%B4))

FINAL STATE: L(%A;%B) L(%B;%C) L(%C;%D) L(%HB;%B2) L(%B2;%B3) REL:B(%HB;%B4) REL:HB(%B1;%B4)

There is no longer a linear relation between %B1 and %B2. The linear relation is now between %B2 and the hyper-node %HB, which contains %B1. The same happens to REL.

RULE#18: REL(%x;%y):=NEWREL(%x;%y)

FINAL STATE: L(%A;%B) L(%B;%C) L(%C;%D) L:B(%B1;%B2) L:B(%B2;%B3) NEWREL:B(%B1;%B4)

The relation is changed, but the arguments %x and %y are preserved.

RULE#19:

REL(%x;%y):=REL(%w;%z)

FINAL STATE: L(%A;%B) L(%B;%C) L(%C;%D) L:B(%B1;%B2) L:B(%B2;%B3) :B(%B4) REL(%w;%z)

The relation between %x and %y is deleted, but the nodes are preserved. Noticed that %B4 became an isolated node, but it’s still there, because no node may be deleted by a NN rule.

INITIAL STATE : REL(%x;%y;%z)

RULE#20: REL(%x;%y;%z):=REL(%x;%y);

FINAL STATE: REL(%x;%y) (%z)

The node %z is not deleted.

INITIAL STATE: L(%A;%B) L(%B;%C) REL:B(%B1;%B2) REL:B(%B1;%B3)

LIST-TO-LIST RULE#21: (REL(%B1;%B3)):=(NEWREL(%B1;%B4));

SAME AS: REL(A;B):=REL(C;D); (if we remove the parentheses from both sides)

FINAL STATE: L(%A;%B) L(%B;%C) REL:B(%B1;%B2) NEWREL:B(%B1;%B4) B:(%B3)

Nodes and relations on both sides are automatically co-indexed, if their number is the same. Therefore, the relation on the left side is replaced by the relation on the right side in the same hyper-node. No node is deleted: notice that %B3 is still there.

LIST-TO-TREE RULE#22: (REL(%B1;%B3)):=NEWREL(%B1;%B4);

SAME AS: ((%x)):=(%x);

FINAL STATE: L(%A;%B) L(%B;%C) REL:B(%B1;%B2) NEWREL(%B1;%B4) B:(%B3)

Nodes and relations on both sides are automatically co-indexed, if their number is the same. Therefore, the relation on the left side is replaced by the relation on the right side BUT OUTSIDE THE HYPER-NODE. No node is deleted. Notice that %B3 is still there inside the hyper-node. Other relations inside the hyper-node are preserved.

TREE-TO-LIST RULE#23: REL(%B1;%B2)REL(%B1;%B3):=(%B1)(%B2);

SAME AS: ((A)):=(A);

FINAL STATE: L(%A;%B) L(%B;%C) L:B(%B1;%B2) :B(%B3)

The node %B3, again, is not deleted, but it does not have any other relation with any other node inside the hyper-node.

Notes

1. ↑ It is important to consider that the resulting order of relations may affect the application of other rules in some implementations. For instance, the rules "SEM(A;B):=SEM(C;D)SEM(E;F);" and "SEM(A;B):= SEM(E;F)SEM(C;D);" will provide the same result, but the relation "SEM(C;D)" may be listed before "SEM(E;F)" in the first case, and after it in the second case. This means that a general rule like SEM(;):=SYN(;);, which would be applicable to both generated relations, will be applied first to "SEM(C;D)" in the first case, and to "SEM(E;F)" in the second case.