Search results for "combinatoric"

A Sokoban-type game and arc deletion within irregular digraphs of all sizes

2007

Cardinal invariants of cellular Lindelof spaces

2018

A space X is said to be cellular-Lindelof if for every cellular family $$\mathcal {U}$$ there is a Lindelof subspace L of X which meets every element of $$\mathcal {U}$$ . Cellular-Lindelof spaces generalize both Lindelof spaces and spaces with the countable chain condition. Solving questions of Xuan and Song, we prove that every cellular-Lindelof monotonically normal space is Lindelof and that every cellular-Lindelof space with a regular $$G_\delta $$ -diagonal has cardinality at most $$2^\mathfrak {c}$$ . We also prove that every normal cellular-Lindelof first-countable space has cardinality at most continuum under $$2^{<\mathfrak {c}}=\mathfrak {c}$$ and that every normal cellular-Lindel…

Optimal Guard Placement Problem Under L-Visibility

2006

Two points a and b in the presence of polygonal obstacles are L-visible if the length of the shortest path avoiding obstacles is no more than L. For a given convex polygon Q, Gewali et al [4]. addressed the guard placement problem on the exterior boundary that will cover the maximum area exterior to the polygon under L-visibility. They proposed a linear time algorithm for some given value of L. When the length L is greater than half of the perimeter, they declared that problem as open. Here we address that open problem and present an algorithm whose time complexity is linear in number of vertices of the polygon.

A NEW COMPLEXITY FUNCTION FOR WORDS BASED ON PERIODICITY

2013

Motivated by the extension of the critical factorization theorem to infinite words, we study the (local) periodicity function, i.e. the function that, for any position in a word, gives the size of the shortest square centered in that position. We prove that this function characterizes any binary word up to exchange of letters. We then introduce a new complexity function for words (the periodicity complexity) that, for any position in the word, gives the average value of the periodicity function up to that position. The new complexity function is independent from the other commonly used complexity measures as, for instance, the factor complexity. Indeed, whereas any infinite word with bound…

Flots de Smale en dimension 3: présentations finies de voisinages invariants d'ensembles selles

2002

Abstract Given a vector field X on a compact 3-manifold, and a hyperbolic saddle-like set K of that vector field, we consider all the filtering neighbourhood of K: by such, we mean any submanifold which boundary is tranverse to X, the maximal invariant of which is equal to K and which intersection with every orbit of X is connected. Up to topological equivalence, there is only a finite number of such neighbourhoods. We give a finite combinatorial presentation of the global dynamics on any such neighbourhood. A key step is the construction of a unique model of the germ of X along K; this model is, roughly speaking, the simplest three-dimensional manifold and the simplest Smale flow exhibitin…

Glorifying Elohim with Dispositive and Probative Facts for Subsequent Motions:Nosce Te Ipsum (A Logic and Mathematics’ Approach)

2018

Pythagoras made the imperative “Man know thyself; then thou shalt know the Universe and God.” One of the Egyptian Luxor Temple proverbs is "Man, know thyself, and you are going to know the gods” and another is "The body is the house of God.” In some ways all classical literature addresses this question. Shakespeare’s asked the famous question, “To be, or not to be, that is the question,” which can be said, “To (X) be (Ǝ), or (V) not (¬) to (X) be (Ǝ), that is (=) the question (a known unknown, ?),” or ((X) Ǝ) V (¬ (X) Ǝ) = ?. Dispositive and probative facts for subsequent motions can be shown as proof of knowing God, which can be simply stated with logic and mathematics: know (cog) God (I) …

On Balancing of a Direct Product

2009

A direct product of two sequences is a naturally defined sequence on the alphabet of pairs of symbols. By taking inspiration from [Pavel Salimov. On uniform recurrence of a direct product. In AutoMathA, 2009], where the author investigates the case of uniformly recurrent words, here, we study when the product of two balanced sequences on binary alphabet is also balanced.

Multiply Transitive Permutation Groups

1982

Since the beginnings of finite group theory, the multiply transitive permutation groups have exercised a certain fascination. This is mainly due to the fact that apart from the symmetric and alternating groups not many of them were known. Only very recently final results about multiply transitive permutation groups have been proved, using the classification of all finite simple groups (see 7.5).

A distance metric on binary trees using lattice-theoretic measures

1990

A so called height function which is a strictly antitone supervaluation is defined on binary trees. Via lattice-theoretic results and using the height function, we can define a distance metric on binary trees of size n which can be computed in expected time O(n 3/2 )

Efficient lower and upper bounds of the diagonal-flip distance between triangulations

2006

There remains today an open problem whether the rotation distance between binary trees or equivalently the diagonal-flip distance between triangulations can be computed in polynomial time. We present an efficient algorithm for computing lower and upper bounds of this distance between a pair of triangulations.