ISSN:
1436-5057
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Summary A binary relation “more canonical than” can be defined for derivationsR, S of a Semi-Thue production system:R〈.S. If there is a canonical (leftmost) derivationK in a class [S] of unessentially different derivations then the transitive closure ≪. of 〈. is an irreflexive ordering. Furtheron, [S] is a finite lattice for which theJordan-Dedekind chain condition is fulfilled. [S] can be embedded as a sublattice into the braid group& which has a lattice structure by the relation of right divisibility.& has a weaker structure than lattice groups in the sense ofLorenzen [8] have. As an extra result we gain a further simple algorithm to solve the word problem for the braid group.
Notes:
Zusammenfassung Zwischen AbleitungenR, S eines Semi-Thue-Produktionensystems kann eine binäre Relation “kanonischer als” definiert werden:R〈.S. Wenn in einer Klasse [S] unwesentlich verschiedener Ableitungen eine kanonische AbleitungK vorkommt, dann ist die transitive Hülle ≪. von 〈. irreflexive Ordnung und macht [S] zu einem endlichen Verband, worin dieJordan-Dedekindsche Kettenbedingung erfüllt ist. [S] ist als Unterverband in die Zopfgruppe& einbettbar, die man vermöge der Rechtsteilbarkeit mit einer Verbandsstruktur versehen kann.& hat eine schwächere Struktur als die Verbandsgruppen im Sinne vonLorenzen [8]. Als Nebenresultat ergibt sich ein weiteres, einfaches Verfahren zur Lösung des Wortproblems für die Zopfgruppe.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02242356
