All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1 Next

Displaying 1 – 20 of 79

Showing per page

A perfect hashing incremental scheme for unranked trees using pseudo-minimal automata

Rafael C. Carrasco, Jan Daciuk (2009)

RAIRO - Theoretical Informatics and Applications

We describe a technique that maps unranked trees to arbitrary hash codes using a bottom-up deterministic tree automaton (DTA). In contrast to other hashing techniques based on automata, our procedure builds a pseudo-minimal DTA for this purpose. A pseudo-minimal automaton may be larger than the minimal one accepting the same language but, in turn, it contains proper elements (states or transitions which are unique) for every input accepted by the automaton. Therefore, pseudo-minimal DTA...

A semantic construction of two-ary integers

Gabriele Ricci (2005)

Discussiones Mathematicae - General Algebra and Applications

To binary trees, two-ary integers are what usual integers are to natural numbers, seen as unary trees. We can represent two-ary integers as binary trees too, yet with leaves labelled by binary words and with a structural restriction. In a sense, they are simpler than the binary trees, they relativize. Hence, contrary to the extensions known from Arithmetic and Algebra, this integer extension does not make the starting objects more complex. We use a semantic construction to get this extension. This...

Characterizing the complexity of boolean functions represented by well-structured graph-driven parity-FBDDs

Henrik Brosenne, Matthias Homeister, Stephan Waack (2002)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We investigate well-structured graph-driven parity-FBDDs, which strictly generalize the two well-known models parity OBDDs and well-structured graph-driven FBDDs. The first main result is a characterization of the complexity of Boolean functions represented by well-structured graph-driven parity-FBDDs in terms of invariants of the function represented and the graph-ordering used. As a consequence, we derive a lower bound criterion and prove an exponential lower bound for certain linear code functions....

Characterizing the Complexity of Boolean Functions represented by Well-Structured Graph-Driven Parity-FBDDs

Henrik Brosenne, Matthias Homeister, Stephan Waack (2010)

RAIRO - Theoretical Informatics and Applications

We investigate well-structured graph-driven parity-FBDDs, which strictly generalize the two well-known models parity OBDDs and well-structured graph-driven FBDDs. The first main result is a characterization of the complexity of Boolean functions represented by well-structured graph-driven parity-FBDDs in terms of invariants of the function represented and the graph-ordering used. As a consequence, we derive a lower bound criterion and prove an exponential lower bound for certain linear code functions. The...

Constructing Binary Huffman Tree

Hiroyuki Okazaki, Yuichi Futa, Yasunari Shidama (2013)

Formalized Mathematics

Huffman coding is one of a most famous entropy encoding methods for lossless data compression [16]. JPEG and ZIP formats employ variants of Huffman encoding as lossless compression algorithms. Huffman coding is a bijective map from source letters into leaves of the Huffman tree constructed by the algorithm. In this article we formalize an algorithm constructing a binary code tree, Huffman tree.

Currently displaying 1 – 20 of 79

Page 1 Next