Search results for "combinatoric"
showing 10 items of 1776 documents
Unambiguous recognizable two-dimensional languages
2006
We consider the family UREC of unambiguous recognizable two-dimensional languages. We prove that there are recognizable languages that are inherently ambiguous, that is UREC family is a proper subclass of REC family. The result is obtained by showing a necessary condition for unambiguous recognizable languages. Further UREC family coincides with the class of picture languages defined by unambiguous 2OTA and it strictly contains its deterministic counterpart. Some closure and non-closure properties of UREC are presented. Finally we show that it is undecidable whether a given tiling system is unambiguous.
Weak and strong recognition by 2-way randomized automata
1997
Languages weakly recognized by a Monte Carlo 2-way finite automaton with n states are proved to be strongly recognized by a Monte Carlo 2-way finite automaton with no(n) states. This improves dramatically over the previously known result by M.Karpinski and R.Verbeek [10] which is also nontrivial since these languages can be nonregular [5]. For tally languages the increase in the number of states is proved to be only polynomial, and these languages are regular.
A note on rank 2 diagonals
2020
<p>We solve two questions regarding spaces with a (G<sub>δ</sub>)-diagonal of rank 2. One is a question of Basile, Bella and Ridderbos about weakly Lindelöf spaces with a G<sub>δ</sub>-diagonal of rank 2 and the other is a question of Arhangel’skii and Bella asking whether every space with a diagonal of rank 2 and cellularity continuum has cardinality at most continuum.</p>
Regularity of renormalized solutions to nonlinear elliptic equations away from the support of measure data
2018
We prove boundedness and continuity for solutions to the Dirichlet problem for the equation $$ - {\rm{div}}(a(x,\nabla u)) = h(x,u) + \mu ,\;\;\;\;\;{\rm{in}}\;{\rm{\Omega }} \subset \mathbb{R}^{N},$$ where the left-hand side is a Leray-Lions operator from $$- {W}^{1,p}_0(\Omega)$$ into W−1,p′(Ω) with 1 < p < N, h(x,s) is a Caratheodory function which grows like ∣s∣p−1 and μ is a finite Radon measure. We prove that renormalized solutions, though not globally bounded, are Holder-continuous far from the support of μ.
The Dirichlet problem for the total variation flow
2001
Suppose that Ω is an open bounded domain with a Lipschitz boundary. The purpose of this chapter is to study the Dirichlet problem $$ \left\{ \begin{gathered} \frac{{\partial u}} {{\partial t}} = div\left( {\frac{{Du}} {{\left| {Du} \right|}}} \right)in Q = \left( {0,\infty } \right) \times \Omega , \hfill \\ u\left( {t,x} \right) = \phi \left( x \right)on S = \left( {0,\infty } \right) \times \partial \Omega , \hfill \\ u\left( {0,x} \right) = u_0 \left( x \right)in x \in \Omega \hfill \\ \end{gathered} \right. $$ (5.1) where u0 ∈ L1(Ω) and ϕ ∈ L1 (∂Ω). This evolution equation is related to the gradient descent method used to solve the problem $$ \begin{gathered} Minimize \int {_\Omega \lef…
Shape optimization for monge-ampére equations via domain derivative
2011
In this note we prove that, if $\Omega$ is a smooth, strictly convex, open set in $R^n$ $(n \ge 2)$ with given measure, the $L^1$ norm of the convex solution to the Dirichlet problem $\det D^2 u=1$ in $\Omega$, $u=0$ on $\partial\Omega$, is minimum whenever $\Omega$ is an ellipsoid.
Leveraging Specific Contexts and Outcomes to Generalize in Combinatorial Settings
2018
International audience; Generalization is a fundamental aspect of mathematics, and it is a practice with which undergraduate students should engage and gain fluency. It is important for students in combinatorial settings to be able to generalize, but combinatorics lends itself to engagement with specific examples, concrete outcomes, and particular contexts. In this paper, we seek to inform the nature of generalization in combinatorial settings by demonstrating ways in which students leverage specific, concrete settings to engage in generalizing activity in combinatorics. We provide two data examples that highlight ways in which concrete and specific ideas can be leveraged to help students d…
Anti-concentration property for random digraphs and invertibility of their adjacency matrices
2016
Let Dn,dDn,d be the set of all directed d-regular graphs on n vertices. Let G be a graph chosen uniformly at random from Dn,dDn,d and M be its adjacency matrix. We show that M is invertible with probability at least View the MathML source1−Cln3d/d for C≤d≤cn/ln2nC≤d≤cn/ln2n, where c,Cc,C are positive absolute constants. To this end, we establish a few properties of directed d-regular graphs. One of them, a Littlewood–Offord-type anti-concentration property, is of independent interest: let J be a subset of vertices of G with |J|≤cn/d|J|≤cn/d. Let δiδi be the indicator of the event that the vertex i is connected to J and δ=(δ1,δ2,…,δn)∈{0,1}nδ=(δ1,δ2,…,δn)∈{0,1}n. Then δ is not concentrate…
An exact method for graph coloring
2006
International audience; We are interested in the graph coloring problem. We propose an exact method based on a linear-decomposition of the graph. The complexity of this method is exponential according to the linearwidth of the entry graph, but linear according to its number of vertices. We present some experiments performed on literature instances, among which COLOR02 library instances. Our method is useful to solve more quickly than other exact algorithms instances with small linearwidth, such as mug graphs. Moreover, our algorithms are the first to our knowledge to solve the COLOR02 instance 4-Inser_3 with an exact method.
Longest Motifs with a Functionally Equivalent Central Block
2004
International audience; This paper presents a generalization of the notion of longest repeats with a block of k don't care symbols introduced by [Crochemore et al., LATIN 2004] (for k fixed) to longest motifs composed of three parts: a first and last that parameterize match (that is, match via some symbol renaming, initially unknown), and a functionally equivalent central block. Such three-part motifs are called longest block motifs. Different types of functional equivalence, and thus of matching criteria for the central block are considered, which include as a subcase the one treated in [Crochemore et al., LATIN 2004] and extend to the case of regular expressions with no Kleene closure or …