index | submit | rank | book

rel-properties – Relation properties

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

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

try first: rel-member triangle

try also: rel-composition

try next: gcd

index | submit | rank | book

Copyright © 2020-2021 Rudy Matela
All rights reserved