On Information Lossless Automata of Finite Order (Q5551176)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3266638
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On Information Lossless Automata of Finite Order |
scientific article; zbMATH DE number 3266638 |
Statements
On Information Lossless Automata of Finite Order (English)
0 references
1965
0 references
automata
0 references
information lossless
0 references
coding graph
0 references
Der Begriff des Automaten \glqq ohne Informationsverlust\grqq{} (information lossless) wird in einer allgemeinen Theorie codierender Graphen (coding graph) ohne Informationsverlust behandelt. Ein codierender Graph ist definiert als endlicher gerichteter Graph, dessen Kanten sämtlich markiert sind. Ein solcher Graph ist ohne Informationsverlust (IL), wenn jeder Weg durch Anfangs- und Endecke und die Markierungen seiner Kanten (in der vorkommenden Reihenfolge) eindeutig bestimmbar ist. Der Graph ist ohne Informationsverlust von endlicher Ordnung (ILF) genau dann, wenn es eine kleinste positive ganze Zahl \(N\) gibt, so daß die erste Kante jedes Weges durch seine Anfangsecke und die ersten \(N\) Markierungen eindeutig bestimmt ist. Für Fälle von praktischem Interesse ist dabei Theorem 1 bedeutsam: Ist ein codierender Graph ILF, und hat er keine Endpunkte, so ist er auch IL. Es werden Algorithmen entwickelt, mit deren Hilfe entschieden werden kann, ob ein gegebener codierender Graph IL bzw. ILF ist. Der Weg führt über einen sogenannten Test-Graphen, wobei gilt: Theorem 3: Ein codierender Graph ist ILF genau dann, wenn sein Test-Graph keine Schleifen hat. Ein brauchbarer Algorithmus, der entscheidet, ob ein Graph eine Schleife hat, läßt sich an der Zusammenhangsmatrix des Graphen vollziehen. Dabei kommt gleichzeitig die Ordnung \(N\) der Informations-Verlustfreiheit heraus. Dieses Verfahren ist auch ohne Schwierigkeiten der Ausführung durch Rechner zugänglich. Die Anwendung des im vorhergehenden Abschnitts entwickelten Algorithmus für endliche Automaten erlaubt Theorem 5: Das Zustandsdiagramm eines Automaten ist ein codierender Graph ohne Endpunkte. Die Arbeit enthält zahlreiche aufschlußreiche Beispiele. Interessant ist vor allem die Methode zur Konstruktion eines Decodierers zu einem gegebenen endlichen Automaten ohne Informationsverlust von endlicher Ordnung als praktische Folgerung aus der Frage nach dem Inversen eines solchen Automaten.
0 references