Search results for "combinatoric"
showing 10 items of 1776 documents
Enumeration of L-convex polyominoes by rows and columns
2005
In this paper, we consider the class of L-convex polyominoes, i.e. the convex polyominoes in which any two cells can be connected by a path of cells in the polyomino that switches direction between the vertical and the horizontal at most once.Using the ECO method, we prove that the number fn of L-convex polyominoes with perimeter 2(n + 2) satisfies the rational recurrence relation fn = 4fn-1 - 2fn-2, with f0 = 1, f1 = 2, f2 = 7. Moreover, we give a combinatorial interpretation of this statement. In the last section, we present some open problems.
Circular sturmian words and Hopcroft’s algorithm
2009
AbstractIn order to analyze some extremal cases of Hopcroft’s algorithm, we investigate the relationships between the combinatorial properties of a circular sturmian word (x) and the run of the algorithm on the cyclic automaton Ax associated to (x). The combinatorial properties of words taken into account make use of sturmian morphisms and give rise to the notion of reduction tree of a circular sturmian word. We prove that the shape of this tree uniquely characterizes the word itself. The properties of the run of Hopcroft’s algorithm are expressed in terms of the derivation tree of the automaton, which is a tree that represents the refinement process that, in the execution of Hopcroft’s alg…
Tree automata, tree decomposition and hyperedge replacement
2005
Recent results concerning efficient solvability of graph problems on graphs with bounded tree-width and decidability of graph properties for hyperedge-replacement graph grammars are systematised by showing how they can be derived from recognisability of corresponding tree classes by finite tree automata, using only well-known techniques from tree-automata theory.
On almost nilpotent varieties of subexponential growth
2015
Abstract Let N 2 be the variety of left-nilpotent algebras of index two, that is the variety of algebras satisfying the identity x ( y z ) ≡ 0 . We introduce two new varieties, denoted by V sym and V alt , contained in the variety N 2 and we prove that V sym and V alt are the only two varieties almost nilpotent of subexponential growth.
Cores for parabolic operators with unbounded coefficients
2009
Abstract Let A = ∑ i , j = 1 N q i j ( s , x ) D i j + ∑ i = 1 N b i ( s , x ) D i be a family of elliptic differential operators with unbounded coefficients defined in R N + 1 . In [M. Kunze, L. Lorenzi, A. Lunardi, Nonautonomous Kolmogorov parabolic equations with unbounded coefficients, Trans. Amer. Math. Soc., in press], under suitable assumptions, it has been proved that the operator G : = A − D s generates a semigroup of positive contractions ( T p ( t ) ) in L p ( R N + 1 , ν ) for every 1 ⩽ p + ∞ , where ν is an infinitesimally invariant measure of ( T p ( t ) ) . Here, under some additional conditions on the growth of the coefficients of A , which cover also some growths with an ex…
(p,q)-summing sequences
2002
Abstract A sequence (x j ) in a Banach space X is (p,q) -summing if for any weakly q -summable sequence (x j ∗ ) in the dual space we get a p -summable sequence of scalars (x j ∗ (x j )) . We consider the spaces formed by these sequences, relating them to the theory of (p,q) -summing operators. We give a characterization of the case p=1 in terms of integral operators, and show how these spaces are relevant for a general question on Banach spaces and their duals, in connection with Grothendieck theorem.
On n–Fold Blocking Sets
1986
An n-fold blocking set is a set of n-disjoint blocking sets. We shall prove upper and lower bounds for the number of components in an n-fold blocking set in projective and affine spaces.
On the longest common factor problem
2008
The Longest Common Factor (LCF) of a set of strings is a well studied problem having a wide range of applications in Bioinformatics: from microarrays to DNA sequences analysis. This problem has been solved by Hui (2000) who uses a famous constant-time solution to the Lowest Common Ancestor (LCA) problem in trees coupled with use of suffix trees. A data structure for the LCA problem, although linear in space and construction time, introduces a multiplicative constant in both space and time that reduces the range of applications in many biological applications. In this article we present a new method for solving the LCF problem using the suffix tree structure with an auxiliary array that take…
Conditional Random Quantities and Iterated Conditioning in the Setting of Coherence
2013
We consider conditional random quantities (c.r.q.’s) in the setting of coherence. Given a numerical r.q. X and a non impossible event H, based on betting scheme we represent the c.r.q. X|H as the unconditional r.q. XH + μH c , where μ is the prevision assessed for X|H. We develop some elements for an algebra of c.r.q.’s, by giving a condition under which two c.r.q.’s X|H and Y|K coincide. We show that X|HK coincides with a suitable c.r.q. Y|K and we apply this representation to Bayesian updating of probabilities, by also deepening some aspects of Bayes’ formula. Then, we introduce a notion of iterated c.r.q. (X|H)|K, by analyzing its relationship with X|HK. Our notion of iterated conditiona…
Countably compact weakly Whyburn spaces
2015
The weak Whyburn property is a generalization of the classical sequential property that was studied by many authors. A space X is weakly Whyburn if for every non-closed set \({A \subset X}\) there is a subset \({B \subset A}\) such that \({\overline{B} \setminus A}\) is a singleton. We prove that every countably compact Urysohn space of cardinality smaller than the continuum is weakly Whyburn and show that, consistently, the Urysohn assumption is essential. We also give conditions for a (countably compact) weakly Whyburn space to be pseudoradial and construct a countably compact weakly Whyburn non-pseudoradial regular space, which solves a question asked by Angelo Bella in private communica…