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: irreflexive, 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. Input is given so that 1 ≤ n ≤ 30.

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

For the purposes of this exercise, you should focus on correctness and not on performance or optimal complexity. Solutions in O(n³), O(n³ log n) or O(n⁵) should be enough to fall within the time limit.

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