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

Previous Page 29 Next

Displaying 561 – 580 of 893

Showing per page

On the decidability of semigroup freeness

Julien Cassaigne, Francois Nicolas (2012)

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

This paper deals with the decidability of semigroup freeness. More precisely, the freeness problem over a semigroup S is defined as: given a finite subset X ⊆ S, decide whether each element of S has at most one factorization over X. To date, the decidabilities of the following two freeness problems have been closely examined. In 1953, Sardinas and Patterson proposed a now famous algorithm for the freeness problem over the free monoids. In 1991, Klarner, Birget and Satterfield proved the undecidability...

On the decidability of semigroup freeness∗

Julien Cassaigne, Francois Nicolas (2012)

RAIRO - Theoretical Informatics and Applications

This paper deals with the decidability of semigroup freeness. More precisely, the freeness problem over a semigroup S is defined as: given a finite subset X ⊆ S, decide whether each element of S has at most one factorization over X. To date, the decidabilities of the following two freeness problems have been closely examined. In 1953, Sardinas and Patterson proposed a now famous algorithm for the freeness problem over the free monoids....

On the distribution of characteristic parameters of words

Arturo Carpi, Aldo de Luca (2002)

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

For any finite word w on a finite alphabet, we consider the basic parameters R w and K w of w defined as follows: R w is the minimal natural number for which w has no right special factor of length R w and K w is the minimal natural number for which w has no repeated suffix of length K w . In this paper we study the distributions of these parameters, here called characteristic parameters, among the words of each length on a fixed alphabet.

On the distribution of characteristic parameters of words

Arturo Carpi, Aldo de Luca (2010)

RAIRO - Theoretical Informatics and Applications

For any finite word w on a finite alphabet, we consider the basic parameters Rw and Kw of w defined as follows: Rw is the minimal natural number for which w has no right special factor of length Rw and Kw is the minimal natural number for which w has no repeated suffix of length Kw. In this paper we study the distributions of these parameters, here called characteristic parameters, among the words of each length on a fixed alphabet.

On the distribution of characteristic parameters of words II

Arturo Carpi, Aldo de Luca (2002)

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

The characteristic parameters K w and R w of a word w over a finite alphabet are defined as follows: K w is the minimal natural number such that w has no repeated suffix of length K w and R w is the minimal natural number such that w has no right special factor of length R w . In a previous paper, published on this journal, we have studied the distributions of these parameters, as well as the distribution of the maximal length of a repetition, among the words of each length on a given alphabet. In this paper...

On the distribution of characteristic parameters of words II

Arturo Carpi, Aldo de Luca (2010)

RAIRO - Theoretical Informatics and Applications

The characteristic parameters Kw and Rw of a word w over a finite alphabet are defined as follows: Kw is the minimal natural number such that w has no repeated suffix of length Kw and Rw is the minimal natural number such that w has no right special factor of length Rw. In a previous paper, published on this journal, we have studied the distributions of these parameters, as well as the distribution of the maximal length of a repetition, among the words of each length on a given alphabet....

On the energy and spectral properties of the he matrix of hexagonal systems

Faqir M. Bhatti, Kinkar Ch. Das, Syed A. Ahmed (2013)

Czechoslovak Mathematical Journal

The He matrix, put forward by He and He in 1989, is designed as a means for uniquely representing the structure of a hexagonal system (= benzenoid graph). Observing that the He matrix is just the adjacency matrix of a pertinently weighted inner dual of the respective hexagonal system, we establish a number of its spectral properties. Afterwards, we discuss the number of eigenvalues equal to zero of the He matrix of a hexagonal system. Moreover, we obtain a relation between the number of triangles...

On the growth rates of complexity of threshold languages

Arseny M. Shur, Irina A. Gorbunova (2010)

RAIRO - Theoretical Informatics and Applications

Threshold languages, which are the (k/(k–1))+-free languages over k-letter alphabets with k ≥ 5, are the minimal infinite power-free languages according to Dejean's conjecture, which is now proved for all alphabets. We study the growth properties of these languages. On the base of obtained structural properties and computer-assisted studies we conjecture that the growth rate of complexity of the threshold language over k letters tends to a constant α ^ ≈ 1 . 242 as k tends to infinity.

On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem

Sounaka Mishra, Kripasindhu Sikdar (2001)

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

We study hardness of approximating several minimaximal and maximinimal NP-optimization problems related to the minimum linear ordering problem (MINLOP). MINLOP is to find a minimum weight acyclic tournament in a given arc-weighted complete digraph. MINLOP is APX-hard but its unweighted version is polynomial time solvable. We prove that MIN-MAX-SUBDAG problem, which is a generalization of MINLOP and requires to find a minimum cardinality maximal acyclic subdigraph of a given digraph, is, however,...

On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem

Sounaka Mishra, Kripasindhu Sikdar (2010)

RAIRO - Theoretical Informatics and Applications

We study hardness of approximating several minimaximal and maximinimal NP-optimization problems related to the minimum linear ordering problem (MINLOP). MINLOP is to find a minimum weight acyclic tournament in a given arc-weighted complete digraph. MINLOP is APX-hard but its unweighted version is polynomial time solvable. We prove that MIN-MAX-SUBDAG problem, which is a generalization of MINLOP and requires to find a minimum cardinality maximal acyclic subdigraph of a given digraph, is, however,...

On the number of binary signed digit representations of a given weight

Jiří Tůma, Jiří Vábek (2015)

Commentationes Mathematicae Universitatis Carolinae

Binary signed digit representations (BSDR’s) of integers have been studied since the 1950’s. Their study was originally motivated by multiplication and division algorithms for integers and later by arithmetics on elliptic curves. Our paper is motivated by differential cryptanalysis of hash functions. We give an upper bound for the number of BSDR’s of a given weight. Our result improves the upper bound on the number of BSDR’s with minimal weight stated by Grabner and Heuberger in On the number of...

Currently displaying 561 – 580 of 893