Search results for "010201 computation theory & mathematics"
showing 10 items of 332 documents
A combinatorial view on string attractors
2021
Abstract The notion of string attractor has recently been introduced in [Prezza, 2017] and studied in [Kempa and Prezza, 2018] to provide a unifying framework for known dictionary-based compressors. A string attractor for a word w = w 1 w 2 ⋯ w n is a subset Γ of the positions { 1 , … , n } , such that all distinct factors of w have an occurrence crossing at least one of the elements of Γ. In this paper we explore the notion of string attractor by focusing on its combinatorial properties. In particular, we show how the size of the smallest string attractor of a word varies when combinatorial operations are applied and we deduce that such a measure is not monotone. Moreover, we introduce a c…
Classifying G-graded algebras of exponent two
2019
Let F be a field of characteristic zero and let $$\mathcal{V}$$ be a variety of associative F-algebras graded by a finite abelian group G. If $$\mathcal{V}$$ satisfies an ordinary non-trivial identity, then the sequence $$c_n^G(\mathcal{V})$$ of G-codimensions is exponentially bounded. In [2, 3, 8], the authors captured such exponential growth by proving that the limit $$^G(\mathcal{V}) = {\rm{lim}}_{n \to \infty} \sqrt[n]{{c_n^G(\mathcal{V})}}$$ exists and it is an integer, called the G-exponent of $$\mathcal{V}$$ . The purpose of this paper is to characterize the varieties of G-graded algebras of exponent greater than 2. As a consequence, we find a characterization for the varieties with …
On operads, bimodules and analytic functors
2017
We develop further the theory of operads and analytic functors. In particular, we introduce a bicategory that has operads as 0-cells, operad bimodules as 1-cells and operad bimodule maps as 2-cells, and prove that this bicategory is cartesian closed. In order to obtain this result, we extend the theory of distributors and the formal theory of monads.
Minimal forbidden patterns of multi-dimensional shifts
2005
We study whether the entropy (or growth rate) of minimal forbidden patterns of symbolic dynamical shifts of dimension 2 or more, is a conjugacy invariant. We prove that the entropy of minimal forbidden patterns is a conjugacy invariant for uniformly semi-strongly irreducible shifts. We prove a weaker invariant in the general case.
On generalised FC-groups in which normality is a transitive relation
2016
We extend to soluble FC∗ -groups, the class of generalised FC-groups introduced in [F. de Giovanni, A. Russo, G. Vincenzi, Groups with restricted conjugacy classes , Serdica Math. J. 28(3) (2002), 241 254], the characterisation of finite soluble T-groups obtained recently in [G. Kaplan, On T-groups, supersolvable groups and maximal subgroups , Arch. Math. 96 (2011), 19 25].
On the Parameterization of Cartesian Genetic Programming
2020
In this work, we present a detailed analysis of Cartesian Genetic Programming (CGP) parametrization of the selection scheme ($\mu+\lambda$), and the levels back parameter l. We also investigate CGP’s mutation operator by decomposing it into a self-recombination, node function mutation, and inactive gene randomization operators. We perform experiments in the Boolean and symbolic regression domains with which we contribute to the knowledge about efficient parametrization of two essential parameters of CGP and the mutation operator.
Motzkin subposets and Motzkin geodesics in Tamari lattices
2014
The Tamari lattice of order n can be defined by the set D n of Dyck words endowed with the partial order relation induced by the well-known rotation transformation. In this paper, we study this rotation on the restricted set of Motzkin words. An upper semimodular join semilattice is obtained and a shortest path metric can be defined. We compute the corresponding distance between two Motzkin words in this structure. This distance can also be interpreted as the length of a geodesic between these Motzkin words in a Tamari lattice. So, a new upper bound is obtained for the classical rotation distance between two Motzkin words in a Tamari lattice. For some specific pairs of Motzkin words, this b…
Gray code for permutations with a fixed number of cycles
2007
AbstractWe give the first Gray code for the set of n-length permutations with a given number of cycles. In this code, each permutation is transformed into its successor by a product with a cycle of length three, which is optimal. If we represent each permutation by its transposition array then the obtained list still remains a Gray code and this allows us to construct a constant amortized time (CAT) algorithm for generating these codes. Also, Gray code and generating algorithm for n-length permutations with fixed number of left-to-right minima are discussed.
On the Non-uniform Redundancy of Representations for Grammatical Evolution: The Influence of Grammars
2018
The representation used in grammatical evolution (GE) is non-uniformly redundant as some phenotypes are represented by more genotypes than others. This article studies how the non-uniform redundancy of the GE representation depends on various types of grammars. When constructing the phenotype tree from a genotype, the used grammar determines Bavg, the average branching factor. Bavg measures the expected number of non-terminals chosen when mapping one genotype codon to a phenotype tree node. First, the paper illustrates that the GE representation induces a bias towards small trees. This bias gets stronger with lower Bavg. For example, when using a grammar with Bavg = 0.5, 75% of all genotype…
Radio Labelings of Distance Graphs
2013
A radio $k$-labeling of a connected graph $G$ is an assignment $c$ of non negative integers to the vertices of $G$ such that $$|c(x) - c(y)| \geq k+1 - d(x,y),$$ for any two vertices $x$ and $y$, $x\ne y$, where $d(x,y)$ is the distance between $x$ and $y$ in $G$. In this paper, we study radio labelings of distance graphs, i.e., graphs with the set $\Z$ of integers as vertex set and in which two distinct vertices $i, j \in \Z$ are adjacent if and only if $|i - j| \in D$.