Title :
Linear time universal coding of tree sources via FSM closure
Author :
Martín, Alvaro ; Seroussi, Gadiel ; Weinberger, Marcelo J.
Author_Institution :
Instituto de Computation, Univ. de la Republica, Montevideo, Uruguay
fDate :
27 June-2 July 2004
Abstract :
This paper presents the first algorithm for linear time encoding/decoding of a twice-universal code in class of tree models. The implemented code is a two-pass (semi-predictive) version of context. The algorithmic tools employed in its derivation and their information-theoretic implications is also investigated. The FSM closure of a generalised context tree, defined as the smallest finite-state machine is characterised.
Keywords :
finite state machines; linear codes; FSM closure; algorithmic tools; finite-state machine; generalised context tree; linear time universal coding; tree sources; Arithmetic; Context modeling; Costs; Decoding; Encoding; Entropy; Laboratories; Milling machines;
Conference_Titel :
Information Theory, 2004. ISIT 2004. Proceedings. International Symposium on
Print_ISBN :
0-7803-8280-3
DOI :
10.1109/ISIT.2004.1365094
