rel-properties – Relation properties – Computer Science by Example

rel-properties – Relation properties

Write a program that is able to list the following properties of binary relations:

reflexive: ∀x, xRx
irreflexive: ∀x, ¬xRx
symmetric: ∀x,y, xRy ⊢ yRx
antisymmetric: ∀x,y, xRy∧yRx ⊢ x=y
asymmetric: ∀x,y, xRy ⊢ ¬yRx
transitive: ∀x,y,z, xRy ∧ yRz ⊢ xRz
equivalence: reflexive, symmetric and transitive
order: reflexive, antisymmetric and transitive
strict order: reflexive, asymmetric and transitive

Relation properties

In this exercise, by convention, we deal with relations over the finite set of natural numbers from 0 to n-1.

Input and output

Input will consist of several relations declared either as a matrix or as a set of ordered pairs.

Each matrix declaration begins with a line containing the word matrix and number n indicating the size of the domain and co-domain. This is followed by n lines with a matrix representation.

Each list declaration begins with a line containing the word list and number n. This is followed by zero or more lines with the ordered pairs of the relation followed by a line containing a dash -.

For each relation given in the input output should contain a list of properties found in the given relation followed by a blank line.

Example Input

matrix 3
0 1 1
0 0 1
0 0 0
list 4
0 0
1 1
2 2
3 3
-

Example Output

irreflexive
antisymmetric
asymmetric
transitive
strict order

reflexive
symmetric
antisymmetric
transitive
equivalence
order

Scoring

1/6: works for the above example but produces output in an incorrect format
2/6: works for the above example and produces output in the correct format
5/6: works for other test cases
6/6: works for edge cases

try first: rel-member triangle

try also: rel-composition

try next: gcd

index | submit | rank | book