Search results for "formal"
showing 10 items of 1654 documents
Super-Exponential Size Advantage of Quantum Finite Automata with Mixed States
2008
Quantum finite automata with mixed states are proved to be super-exponentially more concise rather than quantum finite automata with pure states. It was proved earlier by A.Ambainis and R.Freivalds that quantum finite automata with pure states can have exponentially smaller number of states than deterministic finite automata recognizing the same language. There was a never published "folk theorem" proving that quantum finite automata with mixed states are no more than super-exponentially more concise than deterministic finite automata. It was not known whether the super-exponential advantage of quantum automata is really achievable. We use a novel proof technique based on Kolmogorov complex…
Coding Partitions: Regularity, Maximality and Global Ambiguity
2007
The canonical coding partition of a set of words is the finest partition such that the words contained in at least two factorizations of a same sequence belong to a same class. In the case the set is not uniquely decipherable, it partitions the set into one unambiguous class and other parts that localize the ambiguities in the factorizations of finite sequences. We firstly prove that the canonical coding partition of a regular set contains a finite number of regular classes. We give an algorithm for computing this partition. We then investigate maximality conditions in a coding partition and we prove, in the regular case, the equivalence between two different notions of maximality. As an ap…
A simple proof of the polylog counting ability of first-order logic
2007
The counting ability of weak formalisms (e.g., determining the number of 1's in a string of length N ) is of interest as a measure of their expressive power, and also resorts to complexity-theoretic motivations: the more we can count the closer we get to real computing power. The question was investigated in several papers in complexity theory and in weak arithmetic around 1985. In each case, the considered formalism (AC 0 -circuits, first-order logic, Δ 0 ) was shown to be able to count up to a polylogarithmic number. An essential part of the proofs is the construction of a 1-1 mapping from a small subset of {0, ..., N - 1} into a small initial segment. In each case the expressibility of …
On the Finite Satisfiability Problem for the Guarded Fragment with Transitivity
2005
We study the finite satisfiability problem for the guarded fragment with transitivity. We prove that in case of one transitive predicate the problem is decidable and its complexity is the same as the general satisfiability problem, i.e. 2Exptime-complete. We also show that finite models for sentences of GF with more transitive predicate letters used only in guards have essentially different properties than infinite ones.
Old and New on the Quasihyperbolic Metric
1998
Let D be a proper subdomain of \( {\mathbb{R}^d}\). Following Gehring and Palka [GP] we define the quasihyperbolic distance between a pair x 1, x 2 of points in D as the infimum of \( {\smallint _\gamma }\frac{{ds}}{{D\left( {x,\partial D} \right)}}\) over all rectifiable curves γ joining x 1, x 2 in D. We denote the quasihyperbolic distance between x 1, x 2 by k D (x 1, x 2). As pointed out by Gehring and Osgood [GO], x 1 and x 2 can be joined by a quasihyperbolic geodesic; also see [Mr]. The quasihyperbolic metric is comparable to the usual hyperbolic metric in a simply connected plane domain by the Koebe distortion theorem. For a multiply connected plane domain D these two metrics are co…
Words and forbidden factors
2002
AbstractGiven a finite or infinite word v, we consider the set M(v) of minimal forbidden factors of v. We show that the set M(v) is of fundamental importance in determining the structure of the word v. In the case of a finite word w we consider two parameters that are related to the size of M(w): the first counts the minimal forbidden factors of w and the second gives the length of the longest minimal forbidden factor of w. We derive sharp upper and lower bounds for both parameters. We prove also that the second parameter is related to the minimal period of the word w. We are further interested to the algorithmic point of view. Indeed, we design linear time algorithm for the following two p…
Symbolic Dynamics of Geodesic Flows on Trees
2019
In this chapter, we give a coding of the discrete-time geodesic ow on the nonwandering sets of quotients of locally finite simplicial trees X without terminal vertices by nonelementary discrete subgroups of Aut(X) by a subshift of finite type on a countable alphabet.
Explanation of theΔ5/2−(1930)as aρΔbound state
2009
We use the $\ensuremath{\rho}\ensuremath{\Delta}$ interaction in the hidden gauge formalism to dynamically generate ${N}^{*}$ and ${\ensuremath{\Delta}}^{*}$ resonances. We show, through a comparison of the results from this analysis and from a quark model study with data, that the ${\ensuremath{\Delta}}_{5/{2}^{\ensuremath{-}}}(1930)$, ${\ensuremath{\Delta}}_{3/{2}^{\ensuremath{-}}}(1940)$, and ${\ensuremath{\Delta}}_{1/{2}^{\ensuremath{-}}}(1900)$ resonances can be assigned to $\ensuremath{\rho}\ensuremath{\Delta}$ bound states. More precisely the ${\ensuremath{\Delta}}_{5/{2}^{\ensuremath{-}}}(1930)$ can be interpreted as a $\ensuremath{\rho}\ensuremath{\Delta}$ bound state whereas the $…
Lengths of radii under conformal maps of the unit disc
1999
If E f ( R ) E_{f}(R) is the set of endpoints of radii which have length greater than or equal to R > 0 R>0 under a conformal map f f of the unit disc, then cap E f ( R ) = O ( R − 1 / 2 ) \operatorname {cap} E_{f}(R)=O(R^{-1/2}) as R → ∞ R\to \infty for the logarithmic capacity of E f ( R ) E_{f}(R) . The exponent − 1 / 2 -1/2 is sharp.
Semisimple Lie Algebras
1989
Let F be the field of real or complex numbers. A Lie algebra is a vector space g over F with a Lie product (or commutator) [·,·]: g × g → g such that $$x \mapsto \left[ {x,y} \right]\;is\;linear\;for\;any\;y \in g,$$ (1) $$\left[ {x,y} \right] =- \left[ {y,x} \right],$$ (2) $$\left[ {x,\left[ {y,z} \right]} \right] + \left[ {y,\left[ {z,x} \right]} \right] + \left[ {z,\left[ {x,y} \right]} \right] = 0.$$ (3) The last condition is called the Jacobi identity. From (1) and (2) it follows that also y ↦ [x,y] is linear for any x ∈ g. In this chapter we shall consider only fini te-dimensional Lie algebras. In any vector space g one can always define a trivial Lie product [x,y] = 0. A Lie algebra …