Search results for "Conti"
showing 10 items of 3486 documents
One Alternation Can Be More Powerful Than Randomization in Small and Fast Two-Way Finite Automata
2013
We show a family of languages that can be recognized by a family of linear-size alternating one-way finite automata with one alternation but cannot be recognized by any family of polynomial-size bounded-error two-way probabilistic finite automata with the expected runtime bounded by a polynomial. In terms of finite automata complexity theory this means that neither 1Σ2 nor 1Π2 is contained in 2P2.
Hopcroft's algorithm and tree-like automata
2011
Minimizing a deterministic finite automata (DFA) is a very important problem in theory of automata and formal languages. Hopcroft's algorithm represents the fastest known solution to the such a problem. In this paper we analyze the behavior of this algorithm on a family binary automata, called tree-like automata, associated to binary labeled trees constructed by words. We prove that all the executions of the algorithm on tree-like automata associated to trees, constructed by standard words, have running time with the same asymptotic growth rate. In particular, we provide a lower and upper bound for the running time of the algorithm expressed in terms of combinatorial properties of the trees…
Semi-compatible and reciprocally continuous maps in weak non-Archimedean Menger PM-spaces
2012
In this paper, we introduce semi-compatible maps and reciprocally continuous maps in weak non-Archimedean PM-spaces and establish a common fixed point theorem for such maps. Moreover, we show that, in the context of reciprocal continuity, the notions of compatibility and semi-compatibility of maps become equivalent. Our result generalizes several fixed point theorems in the sense that all maps involved in the theorem can be discontinuous even at the common fixed point.
2-SYMMETRIC CRITICAL POINT THEOREMS FOR NON-DIFFERENTIABLE FUNCTIONS
2008
AbstractIn this paper, some min–max theorems for even andC1functionals established by Ghoussoub are extended to the case of functionals that are the sum of a locally Lipschitz continuous, even term and a convex, proper, lower semi-continuous, even function. A class of non-smooth functionals admitting an unbounded sequence of critical values is also pointed out.
Rademacher Theorem for Fréchet spaces
2010
Abstract Let X be a separable Frechet space. In this paper we define a class A of null sets in X that is properly contained in the class of Aronszajn null sets, and we prove that a Lipschitz map from an open subset of X into a Gelfand-Frechet space is Gateaux differentiable outside a set belonging to A. This is an extension to Frechet spaces of a result (see [PZ]) due to D. Preiss and L. Zajicek.
On the equivalence of McShane and Pettis integrability in non-separable Banach spaces
2009
Abstract We show that McShane and Pettis integrability coincide for functions f : [ 0 , 1 ] → L 1 ( μ ) , where μ is any finite measure. On the other hand, assuming the Continuum Hypothesis, we prove that there exist a weakly Lindelof determined Banach space X, a scalarly null (hence Pettis integrable) function h : [ 0 , 1 ] → X and an absolutely summing operator u from X to another Banach space Y such that the composition u ○ h : [ 0 , 1 ] → Y is not Bochner integrable; in particular, h is not McShane integrable.
On the solutions to 1-Laplacian equation with L1 data
2009
AbstractIn the present paper we study the behaviour, as p goes to 1, of the renormalized solutions to the problems(0.1){−div(|∇up|p−2∇up)=finΩ,up=0on∂Ω, where p>1, Ω is a bounded open set of RN (N⩾2) with Lipschitz boundary and f belongs to L1(Ω). We prove that these renormalized solutions pointwise converge, up to “subsequences,” to a function u. With a suitable definition of solution we also prove that u is a solution to a “limit problem.” Moreover we analyze the situation occurring when more regular data f are considered.
Quantum Finite Multitape Automata
1999
Quantum finite automata were introduced by C. Moore, J. P. Crutchfield [4], and by A. Kondacs and J. Watrous [3]. This notion is not a generalization of the deterministic finite automata. Moreover, in [3] it was proved that not all regular languages can be recognized by quantum finite automata. A. Ambainis and R. Freivalds [1] proved that for some languages quantum finite automata may be exponentially more concise rather than both deterministic and probabilistic finite automata. In this paper we introduce the notion of quantum finite multitape automata and prove that there is a language recognized by a quantum finite automaton but not by deterministic or probabilistic finite automata. This …
Probabilistic Reversible Automata and Quantum Automata
2002
To study relationship between quantum finite automata and probabilistic finite automata, we introduce a notion of probabilistic reversible automata (PRA, or doubly stochastic automata). We find that there is a strong relationship between different possible models of PRA and corresponding models of quantum finite automata. We also propose a classification of reversible finite 1-way automata.
Specification on the interval
1997
We study the consequences of discontinuities on the specification property for interval maps. After giving a necessary and sufficient condition for a piecewise monotonic, piecewise continuous map to have this property, we show that for a large and natural class of families of such maps (including the β \beta -transformations), the set of parameters for which the specification property holds, though dense, has zero Lebesgue measure. Thus, regarding the specification property, the general case is at the opposite of the continuous case solved by A.M. Blokh (Russian Math. Surveys 38 (1983), 133–134) (for which we give a proof).