Page 1 Next

Displaying 1 – 20 of 23

Showing per page

A hierarchy for circular codes

Giuseppe Pirillo (2008)

RAIRO - Theoretical Informatics and Applications

We first prove an extremal property of the infinite Fibonacci* word f: the family of the palindromic prefixes {hn | n ≥ 6} of f is not only a circular code but “almost” a comma-free one (see Prop. 12 in Sect. 4). We also extend to a more general situation the notion of a necklace introduced for the study of trinucleotides codes on the genetic alphabet, and we present a hierarchy relating two important classes of codes, the comma-free codes and the circular ones.

Access structures for finding characteristic-dependent linear rank inequalities

Victor Peña-Macias (2023)

Kybernetika

Determining information ratios of access structures is an important problem in secret sharing. Information inequalities and linear rank inequalities play an important role for proving bounds on these ratios. Characteristic-dependent linear rank inequalities are rank inequalities which are true over vector spaces with specific field characteristic. In this paper, using ideas of secret sharing, we show a theorem that produces characteristic-dependent linear rank inequalities. These inequalities are...

Applying A Normalized Compression Metric To The Measurement Of Dialect Distance

Simov, Kiril, Osenova, Petya (2007)

Serdica Journal of Computing

The paper discusses the application of a similarity metric based on compression to the measurement of the distance among Bulgarian dia- lects. The similarity metric is de ned on the basis of the notion of Kolmo- gorov complexity of a le (or binary string). The application of Kolmogorov complexity in practice is not possible because its calculation over a le is an undecidable problem. Thus, the actual similarity metric is based on a real life compressor which only approximates the Kolmogorov complexity....

Combining adaptive vector quantization and prototype selection techniques to improve nearest neighbour classifiers

Francesc J. Ferri (1998)

Kybernetika

Prototype Selection (PS) techniques have traditionally been applied prior to Nearest Neighbour (NN) classification rules both to improve its accuracy (editing) and to alleviate its computational burden (condensing). Methods based on selecting/discarding prototypes and methods based on adapting prototypes have been separately introduced to deal with this problem. Different approaches to this problem are considered in this paper and their main advantages and drawbacks are pointed out along with some...

Compression of satellite data.

Roberto Barrio, Antonio Elipe (2002)

Revista Matemática Complutense

In this paper, we present the simple and double compression algorithms with an error control for compressing satellite data corresponding to several revolutions. The compressions are performed by means of approximations in the norm L∞ by finite series of Chebyshev polynomials, with their known properties of fast evaluation, uniform distribution of the error, and validity over large intervals of time. By using the error control here introduced, the number of terms of the series is given automatically...

Conceptual Information Compression and Efficient Pattern Search

Angelova, Galia, Mihov, Stoyan (2008)

Serdica Journal of Computing

This paper introduces an encoding of knowledge representation statements as regular languages and proposes a two-phase approach to processing of explicitly declared conceptual information. The idea is presented for the simple conceptual graphs where conceptual pattern search is implemented by the so called projection operation. Projection calculations are organised into off-line preprocessing and run-time computations. This enables fast run-time treatment of NP-complete problems, given that the intermediate...

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.

Edon- ( 256 , 384 , 512 ) – an efficient implementation of Edon- family of cryptographic hash functions

Danilo Gligoroski, Svein Johan Knapskog (2008)

Commentationes Mathematicae Universitatis Carolinae

We have designed three fast implementations of a recently proposed family of hash functions Edon– . They produce message digests of length n = 256 , 384 , 512 bits and project security of 2 n 2 hash computations for finding collisions and 2 n hash computations for finding preimages and second preimages. The design is not the classical Merkle-Damgård but can be seen as wide-pipe iterated compression function. Moreover the design is based on using huge quasigroups of orders 2 256 , 2 384 and 2 512 that are constructed by using only bitwise...

Finite completion of comma-free codes. Part 1

Nguyen Huong Lam (2004)

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

This paper is the first step in the solution of the problem of finite completion of comma-free codes. We show that every finite comma-free code is included in a finite comma-free code of particular kind, which we called, for lack of a better term, canonical comma-free code. Certainly, finite maximal comma-free codes are always canonical. The final step of the solution which consists in proving further that every canonical comma-free code is completed to a finite maximal comma-free code, is intended...

Finite Completion of comma-free codes Part 1

Nguyen Huong Lam (2010)

RAIRO - Theoretical Informatics and Applications

This paper is the first step in the solution of the problem of finite completion of comma-free codes. We show that every finite comma-free code is included in a finite comma-free code of particular kind, which we called, for lack of a better term, canonical comma-free code. Certainly, finite maximal comma-free codes are always canonical. The final step of the solution which consists in proving further that every canonical comma-free code is completed to a finite maximal comma-free code, is intended...

Finite completion of comma-free codes. Part 2

Nguyen Huong Lam (2004)

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

This paper is a sequel to an earlier paper of the present author, in which it was proved that every finite comma-free code is embedded into a so-called (finite) canonical comma-free code. In this paper, it is proved that every (finite) canonical comma-free code is embedded into a finite maximal comma-free code, which thus achieves the conclusion that every finite comma-free code has finite completions.

Finite Completion of comma-free codes Part 2

Nguyen Huong Lam (2010)

RAIRO - Theoretical Informatics and Applications

This paper is a sequel to an earlier paper of the present author, in which it was proved that every finite comma-free code is embedded into a so-called (finite) canonical comma-free code. In this paper, it is proved that every (finite) canonical comma-free code is embedded into a finite maximal comma-free code, which thus achieves the conclusion that every finite comma-free code has finite completions.


FSM encoding for BDD representations

Wilsin Gosti, Tiziano Villa, Alex Saldanha, Alberto Sangiovanni-Vincentelli (2007)

International Journal of Applied Mathematics and Computer Science

We address the problem of encoding the state variables of a finite state machine such that the BDD representing the next state function and the output function has the minimum number of nodes. We present an exact algorithm to solve this problem when only the present state variables are encoded. We provide results on MCNC benchmark circuits.

Noise Shaping in Neural Populations with Global Delayed Feedback

O. Ávila Åkerberg, M. J. Chacron (2010)

Mathematical Modelling of Natural Phenomena

The interplay between intrinsic and network dynamics has been the focus of many investigations. Here we use a combination of theoretical and numerical approaches to study the effects of delayed global feedback on the information transmission properties of neural networks. Specifically, we compare networks of neurons that display intrinsic interspike interval correlations (nonrenewal) to networks that do not (renewal). We find that excitatory and...

On the size of transducers for bidirectional decoding of prefix codes

Laura Giambruno, Sabrina Mantaci (2012)

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

In a previous paper [L. Giambruno and S. Mantaci, Theoret. Comput. Sci. 411 (2010) 1785–1792] a bideterministic transducer is defined for the bidirectional deciphering of words by the method introduced by Girod [IEEE Commun. Lett. 3 (1999) 245–247]. Such a method is defined using prefix codes. Moreover a coding method, inspired by the Girod’s one, is introduced, and a transducer that allows both right-to-left and left-to-right decoding by this method is defined. It is proved also that this transducer...

On the size of transducers for bidirectional decoding of prefix codes

Laura Giambruno, Sabrina Mantaci (2012)

RAIRO - Theoretical Informatics and Applications

In a previous paper [L. Giambruno and S. Mantaci, Theoret. Comput. Sci. 411 (2010) 1785–1792] a bideterministic transducer is defined for the bidirectional deciphering of words by the method introduced by Girod [IEEE Commun. Lett. 3 (1999) 245–247]. Such a method is defined using prefix codes. Moreover a coding method, inspired by the Girod’s one, is introduced, and a transducer that allows both right-to-left and left-to-right decoding by this...

Currently displaying 1 – 20 of 23

Page 1 Next