isomorph

Name

isomorph -- test two machines for isomorphism

Synopsis

isomorph fm1 fm2

isomorph fm2 <fm1

Description

isomorph tests fm1 and fm2 for isomorphism. isomorph returns 1 and writes isomorphic on standard output if the two machines are isomorphic, and returns 0 and writes nonisomorphic otherwise.

If two machines are not input, isomorph writes a diagnostic on standard error and returns 0. If either machine is not deterministic, isomorph returns -1 and writes a diagnostic on its standard error. A machine can be made deterministic by filtering it with fmdeterm.

Two machines are isomorphic if they are equivalent up to renumbering. Isomorphism is checked by applying canonical numbering to each machine and then testing for identity.

fm1 and fm2 must conform to the Grail format for machines.

Examples

% cat dfm4
(START) |- 0
0 a 1
0 g 0
0 b 4
1 c 2
2 d 3
3 -| (FINAL)
4 e 5
5 f 6
6 -| (FINAL)

% isomorph dfm4 dfm4
isomorphic

% cat dfm1
(START) |- 0
0 a 1
1 b 2
2 -| (FINAL)

% cat dfm2
(START) |- 3
3 a 4
4 b 5
5 -| (FINAL)

% isomorph dfm1 dfm2
isomorphic

% isomorph dfm1 dfm4
nonisomorphic

% isomorph dfm1 nfm1
nonisomorphic

Authors