congruence

congruence

Congruence or G-congruence (graph congruence) checks whether two sequences (one a permutation of the other) or derivations have the same initial digraphs. It is studied in detail in Sec. 6.1 in the MGG book.

Congruence is used to characterize sequential independence: If the sequence and its permutation are both compatible, coherent and congruent, then they are sequentially independent, i.e. they can be applied to the same initial graph and will eventually derive the same image graph.

Sequential independence means that the ordering of the productions (at least the two orderings specified by these sequences) do not affect the inital nor the final states.

In the MGG book there are some formulas that guarantee congruence in case of a single production being advanced a finite number of positions inside a sequence. They are known as congruence conditions. They can be calculated during design time, while the grammar is being defined, i.e. they are independent to some extent of the initial graph the sequence is going to be applied to.

Albert Einstein: Do not worry about your difficulties in Mathematics. I can assure you mine are still greater.