Displaying 21 – 40 of 4960

Showing per page

A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata

Daniel Kirsten (2008)

RAIRO - Theoretical Informatics and Applications

We show that the termination of Mohri's algorithm is decidable for polynomially ambiguous weighted finite automata over the tropical semiring which gives a partial answer to a question by Mohri [29]. The proof relies on an improvement of the notion of the twins property and a Burnside type characterization for the finiteness of the set of states produced by Mohri's algorithm.

A. C. Clarke's Space Odyssey and Newton's law of gravity

Bartoň, Stanislav, Renčín, Lukáš (2017)

Programs and Algorithms of Numerical Mathematics

In his famous tetralogy, Space Odyssey, A. C. Clarke called the calculation of a motion of a mass point in the gravitational field of the massive cuboid a classical problem of gravitational mechanics. This article presents a proposal for a solution to this problem in terms of Newton's theory of gravity. First we discuss and generalize Newton's law of gravitation. We then compare the gravitational field created by the cuboid -- monolith, with the gravitational field of the homogeneous sphere. This...

A CAT algorithm for the exhaustive generation of ice piles

Paolo Massazza, Roberto Radicioni (2010)

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

We present a CAT (constant amortized time) algorithm for generating those partitions of n that are in the ice pile model IPM k (n), a generalization of the sand pile model SPM (n). More precisely, for any fixed integer k, we show that the negative lexicographic ordering naturally identifies a tree structure on the lattice IPM k (n): this lets us design an algorithm which generates all the ice piles of IPM k (n) in amortized time O(1) and in space O( n ).

A CAT algorithm for the exhaustive generation of ice piles

Paolo Massazza, Roberto Radicioni (2011)

RAIRO - Theoretical Informatics and Applications

We present a CAT (constant amortized time) algorithm for generating those partitions of n that are in the ice pile model IPM k (n), a generalization of the sand pile model SPM (n). More precisely, for any fixed integer k, we show that the negative lexicographic ordering naturally identifies a tree structure on the lattice IPM k (n): this lets us design an algorithm which generates all the ice piles of IPM k (n) in amortized time O(1) and in space O( n ).

A categorical view at generalized concept lattices

Stanislav Krajči (2007)

Kybernetika

We continue in the direction of the ideas from the Zhang’s paper [Z] about a relationship between Chu spaces and Formal Concept Analysis. We modify this categorical point of view at a classical concept lattice to a generalized concept lattice (in the sense of Krajči [K1]): We define generalized Chu spaces and show that they together with (a special type of) their morphisms form a category. Moreover we define corresponding modifications of the image / inverse image operator and show their commutativity...

A chaos-based secure cluster protocol for wireless sensor networks

Qian Fang, Ying Liu, Xiaoqun Zhao (2008)

Kybernetika

Security mechanisms for wireless sensor networks (WSN) face a great challenge due to the restriction of their small sizes and limited energy. Hence, many protocols for WSN are not designed with the consideration of security. Chaotic cryptosystems have the advantages of high security and little cost of time and space, so this paper proposes a secure cluster routing protocol based on chaotic encryption as well as a conventional symmetric encryption scheme. First, a principal-subordinate chaotic function...

A characterization for residuated implications on the set of all the closed intervals in J[0,1]. Application to the L-fuzzy concept theory.

Cristina Alcalde, Ana Burusco, Ramón Fuentes-González (2005)

Mathware and Soft Computing

In this paper, a new characterization for the interval-valued residuated fuzzy implication operators is presented, with which it is possible to use them in a simple and efficient way, since the calculation of the values of an intervalvalued implication applicated to two intervals is reduced to the study of a fuzzy implication applicated to the extremes of these intervals. This result is very important in order to extract knowledge from an L-fuzzy context with incomplete information. Finally, some...

A Characterization of Multidimensional S -Automatic Sequences

Emilie Charlier, Tomi Kärki, Michel Rigo (2009)

Actes des rencontres du CIRM

An infinite word is S -automatic if, for all n 0 , its ( n + 1 ) st letter is the output of a deterministic automaton fed with the representation of n in the considered numeration system S . In this extended abstract, we consider an analogous definition in a multidimensional setting and present the connection to the shape-symmetric infinite words introduced by Arnaud Maes. More precisely, for d 2 , we state that a multidimensional infinite word x : d Σ over a finite alphabet Σ is S -automatic for some abstract numeration...

A characterization of poly-slender context-free languages

Lucian Ilie, Grzegorz Rozenberg, Arto Salomaa (2010)

RAIRO - Theoretical Informatics and Applications

For a non-negative integer k, we say that a language L is k-poly-slender if the number of words of length n in L is of order 𝒪 ( n k ) . We give a precise characterization of the k-poly-slender context-free languages. The well-known characterization of the k-poly-slender regular languages is an immediate consequence of ours.

A chunking mechanism in a neural system for the parallel processing of propositional production rules.

Ernesto Burattini, A. Pasconcino, Guglielmo Tamburrini (1995)

Mathware and Soft Computing

The problem of extracting more compact rules from a rule-based knowledge base is approached by means of a chunking mechanism implemented via a neural system. Taking advantage of the parallel processing potentialities of neural systems, the computational problem normally arising when introducing chuncking processes is overcome. Also the memory saturation effect is coped with using some sort of forgetting mechanism which allows the system to eliminate previously stored, but less often used chunks....

Currently displaying 21 – 40 of 4960