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.

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

try first: rel-member triangle

try also: rel-composition

try next: gcd

index | submit | rank | book

Copyright © 2020-2021 Rudy Matela
All rights reserved