Transitive Closure and Reflexive-Transitive Closure \(R^+, R^*\)

Closure (Mathematics)

Closure is a property said to be satisfied by a set under a given operation if and only if performing the operation on members of the set always produces a member of the same set. (Wikipedia)

• binary relation: 2-ary relation (\(R \subseteq S \times S\))
• P closure operator: cl(R) is the strongest or the smallest relation (\(cl(R) \subseteq S \times S\)) that contains R (\(R \subseteq cl(R)\)) and the property P holds (P(Q)=true).
• a binary relation R is transitive: \(\forall x,y,z: S \bullet (((x,y) \in R \land (y, z) \in R) \implies (x,z) \in R)\)
• for example, \(>, =, \geq, \leq\) are transitive, but "is parent of" is not.
• a binary relation R is reflexive: \(\forall x: S \bullet ((x,x) \in R)\)
• for example, \(=,\geq,\leq\) are reflexive, but > is not reflexive

For example,

• reflexive closure: \(cl_{ref}(R)\) is the smallest relation that contains R and is reflexive.
• transitive closure: \(cl_{trn}(R)\), or \(R^+\) is the smallest relation that contains R and is transitive.
• reflexive–transitive closure: \(R^*\) is the smallest relation that contains R and is both transitive and reflexive.

Definitions

• \(R^r=R \cup id\ S\) - reflexive closure
• \(R^s=R \cup R^\sim\) - symmetric closure 
• \(R^*=R^+ \cup id\ S\)

Alternative Definitions in terms of iterations (Z notation)

• iteration of relation: \(R^k=R;R;...;R = R;R^{k-1}=R^{k-1};R\)
• \(R^0=id\ S\)
• \(R^+=\bigcup\{k:\mathbb{N}_1 \bullet R^k\}\) 
• \(R^+=\bigcup\{k:\mathbb{N} \bullet R^k\}\) 

Applications

• transitive closure of a directed graph likes cities connection by railways or airplanes: means all possible routes from one city to another city, then can be used to calculate the shortest path from one place to another place
• \(R = \{(A,B),(B,C),(B,D),(C,A)\}\) - direct routes between two cities
• \(R^2=R;R=\{(A,C), (A,D),(B,A),(C,B)\}\) - one stop routes between two cities
• \(R^3=R^2;R=\{(A,C), (A,D),(B,A),(C,B)\};\{(A,B),(B,C),(B,D),(C,A)\}=\{(A,A),(B,B),(C,C),(C,D)\}\) - two stop routes between two cities
• \(R^4=R^3;R=\{(A,A),(B,B),(C,C),(C,D)\};\{(A,B),(B,C),(B,D),(C,A)\}=\{(A,B),(B,C),(B,D),(C,A)\}\) - equal to R
• finally, \(R^+=R \cup R^2 \cup R^3=\{(A,B),(B,C),(B,D),(C,A),(A,C), (A,D),(B,A),(C,B),(A,A),(B,B),(C,C),(C,D)\}\)

Example

[Logic] Arguments, Validity, Soundness and Completeness

Arguments:

In logic and philosophy, an argument is a series of statements typically used to persuade someone of something or to present reasons for accepting a conclusion [Wikipedia]

An argument consists of one or more premises and only one conclusion.

Another reference is here.

 Deductive arguments

The conclusion is a logic consequence of the premises. It is based on the premises and then the conclusion follows necessarily.

 Inductive arguments

An inductive argument is an argument that is intended by the arguer merely to establish or increase the probability of its conclusion. [Encyclopedia]

 Validity

 A valid deductive argument guarantees the truth of the conclusion provided the premises are true, regardless of the reality of the premises, by following logic form. Being a valid deductive argument, if all premises are true, the conclusion is impossibly false (must be true).

A --> B
A
--------
B

This is a valid argument no matter whether A and (A-->B) are possibly true or not in real.

Soundness

A sound argument is a valid argument and the premises are true in real.

Validity vs. Soundness

In the example above,

• if A and B stand for "All trains travel faster than cars" and "No one will travel by car", then the argument is valid but not sound because two premises are not true in real. 
•  The argument such as  "All even numbers can be divided by 2; 4 is a even number; therefore 4 can be divided by 2", is valid and sound.

Completeness

A system is said to be complete if something is really true, the system is capable of proving it.

Soundness vs. Completeness

A good way to understand these definitions is that soundness prevents false negatives and completeness prevents false positives. [from note]

False negatives mean "tested to be true actually it is false". Soundness prevents "something is said to be true but actually is not true". It guarantees that "if something is said to be true, it really is true."

False positives mean "tested to be false actually it is true". Completeness prevents "something is said to be false but actually is not false". It guarantees that "all true things are provable."

A sound logic proves only true things. A complete logic proves all true things. [from note]

Shift/Reduce demonstration - 2 [Happy]

Happy is a LALR(1) parser.

The production: (to get an expression)

Expr16 :: Expr16 'cross' Expr17
             | Expr17

 The syntax to demonstrate:

ZED X == A x B x C END

Shift/Reduce demonstration - 1 [Happy]

Happy is a LALR(1) parser.

The production: (to get an expression)

Expr16 :: Expr17 'cross' Expr16
             | Expr17

 The syntax to demonstrate:

ZED X == A x B x C END

1st part

2nd part

Summary

Shift/Reduce demonstration - 0 [Happy]

Happy is a LALR(1) parser.

Left Associativity

The production (as shown).
Two expressions ( 1 + 1 + 1, and 1 + 1 * 1)  are demonstrated.

 

Finally, Exp3 will be reduced to Expression.

Right Associativity

The production (as shown).
One expression ( 1 + 1 + 1)  is demonstrated.

Finally, Exp3 will be reduced to Expression.

 

LL, LR, LALR, GLR ...

• Top-down parser

Beginning with the start symbol, try to guess the productions to apply to end up at the user's program. An example from this slide is shown below

 


First it starts from E and guesses "E --> T + E" to apply, then "T --> int", and "E --> T", " T -> (E)", "E --> T + E", "T --> int", "E --> T", finally "T --> int"


•  LL(1) 
• first 'L' - read the input from left to right.
• second 'L' - descend into parse tree children from left to right (Leftmost derivation).
• 1 - a single lookahead token 
• Predict/match parser

• LL(2)
• 2 - two lookahead tokens

• Bottom-Up parser

Beginning with the user's program, try to apply productions in reverse to convert the program back into the start symbol. Another example from this slide is illustrated.

 

 Start from "int + (int + int + int)", apply the reverse of the production "T -> int": "int -> T" and get 

• int -> T :           T + (int + int + int)
• T -> E:              E + (int + int + int)
• int -> T:            E + (T + int + int)
• T -> E:              E + (E + int + int)  
• int -> T:            E + (E + T + int)
• E + T -> E:       E + (E + int)
• int -> T:            E + (E + T)
• E + T -> E:       E + (E)
• (E) -> T:           E + T
• E + T -> E:       E

• SLR
• Simple LR(1)
• LR(0), LR(1), LR(k)...
• first 'L' - read the input from left to right.
• second 'R' - reversed Rightmost derivation.
• 1 - a single lookahead token 
• LR(1) is very powerful
•  LALR
• Look-Ahead LR parser is a variant of LR
• LALR(1): Look-Ahead (1) LR(0)

•  GLR
• generalized LR: an extension of LR
• handle nondeterministic and ambiguous grammars

• Shift/reduce parser 
• A parsing method for LR parser
• Split input stream into two substrings: only process left substring and right substring is unseen.
• Shift: move the separate bar in the input stream by one token (left to right)
• Reduce: apply productions to left substring to get a new parser tree
• Shift/Reduce conflict: an error where a shift/reduce parser cannot tell whether to shift a token or perform a reduction.
• Often happens when two productions overlap.
• Reduce/Reduce conflict: an error where a shift/reduce parser cannot tell which of many reductions to perform.
• Often the result of ambiguous grammars.
• Reference: this slide and this video