Search results for "Computation theory"
showing 10 items of 336 documents
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$.
Languages associated with saturated formations of groups
2013
International audience; In a previous paper, the authors have shown that Eilenberg's variety theorem can be extended to more general structures, called formations. In this paper, we give a general method to describe the languages corresponding to saturated formations of groups, which are widely studied in group theory. We recover in this way a number of known results about the languages corresponding to the classes of nilpotent groups, soluble groups and supersoluble groups. Our method also applies to new examples, like the class of groups having a Sylow tower.; Dans un article précédent, les auteurs avaient montré comment étendre le théorème des variétés d'Eilenberg à des structures plus g…
Regularity and h-polynomials of toric ideals of graphs
2020
For all integers 4 ≤ r ≤ d 4 \leq r \leq d , we show that there exists a finite simple graph G = G r , d G= G_{r,d} with toric ideal I G ⊂ R I_G \subset R such that R / I G R/I_G has (Castelnuovo–Mumford) regularity r r and h h -polynomial of degree d d . To achieve this goal, we identify a family of graphs such that the graded Betti numbers of the associated toric ideal agree with its initial ideal, and, furthermore, that this initial ideal has linear quotients. As a corollary, we can recover a result of Hibi, Higashitani, Kimura, and O’Keefe that compares the depth and dimension of toric ideals of graphs.
In the Shadows of a hypergraph: looking for associated primes of powers of squarefree monomial ideals
2018
The aim of this paper is to study the associated primes of powers of square-free monomial ideals. Each square-free monomial ideal corresponds uniquely to a finite simple hypergraph via the cover ideal construction, and vice versa. Let H be a finite simple hypergraph and J(H) the cover ideal of H. We define the shadows of hypergraph, H, described as a collection of smaller hypergraphs related to H under some conditions. We then investigate how the shadows of H preserve information about the associated primes of the powers of J(H). Finally, we apply our findings on shadows to study the persistence property of square-free monomial ideals and construct some examples exhibiting failure of contai…
An Efficient Algorithm for Helly Property Recognition in a Linear Hypergraph
2001
International audience; In this article we characterize bipartite graphs whose associated neighborhood hypergraphs have the Helly property. We examine incidence graphs both hypergraphs and linear hypergraphs and we give a polynomial algorithm to recognize if a linear hypergraph has the Helly property.
Steiner configurations ideals: Containment and colouring
2021
Given a homogeneous ideal I&sube
Defining Interaction Design Patterns to Extract Knowledge from Big Data
2018
[EN] The Big Data domain offers valuable opportunities to gain valuable knowledge. The User Interface (UI), the place where the user interacts to extract knowledge from data, must be adapted to address the domain complexities. Designing UIs for Big Data becomes a challenge that involves identifying and designing the user-data interaction implicated in the knowledge extraction. To design such an interaction, one widely used approach is design patterns. Design Patterns describe solutions to common interaction design problems. This paper proposes a set of patterns to design UIs aimed at extracting knowledge from the Big Data systems data conceptual schemas. As a practical example, we apply the…
Codimensions of star-algebras and low exponential growth
2020
In this paper we prove that if A is any algebra with involution * satisfying a non-trivial polynomial identity, then its sequence of *-codimensions is eventually non-decreasing. Furthermore, by making use of the *-exponent we reconstruct the only two *-algebras, up to T*-equivalence, generating varieties of almost polynomial growth. As a third result we characterize the varieties of algebras with involution whose exponential growth is bounded by 2.