Search results for "Mathematica"

The Monadic Quantifier Alternation Hierarchy over Grids and Graphs

2002

AbstractThe monadic second-order quantifier alternation hierarchy over the class of finite graphs is shown to be strict. The proof is based on automata theoretic ideas and starts from a restricted class of graph-like structures, namely finite two-dimensional grids. Considering grids where the width is a function of the height, we prove that the difference between the levels k+1 and k of the monadic hierarchy is witnessed by a set of grids where this function is (k+1)-fold exponential. We then transfer the hierarchy result to the class of directed (or undirected) graphs, using an encoding technique called strong reduction. It is notable that one can obtain sets of graphs which occur arbitrar…

Nonlinear embeddings: Applications to analysis, fractals and polynomial root finding

2016

We introduce $\mathcal{B}_{\kappa}$-embeddings, nonlinear mathematical structures that connect, through smooth paths parameterized by $\kappa$, a finite or denumerable set of objects at $\kappa=0$ (e.g. numbers, functions, vectors, coefficients of a generating function...) to their ordinary sum at $\kappa \to \infty$. We show that $\mathcal{B}_{\kappa}$-embeddings can be used to design nonlinear irreversible processes through this connection. A number of examples of increasing complexity are worked out to illustrate the possibilities uncovered by this concept. These include not only smooth functions but also fractals on the real line and on the complex plane. As an application, we use $\mat…

On algebras of polynomial codimension growth

2016

Let A be an associative algebra over a field F of characteristic zero and let $$c_n(A), n=1, 2, \ldots $$ , be the sequence of codimensions of A. It is well-known that $$c_n(A), n=1, 2, \ldots $$ , cannot have intermediate growth, i.e., either is polynomially bounded or grows exponentially. Here we present some results on algebras whose sequence of codimensions is polynomially bounded.

Implications of quantum automata for contextuality

2014

We construct zero error quantum finite automata (QFAs) for promise problems which cannot be solved by bounded error probabilistic finite automata (PFAs). Here is a summary of our results: There is a promise problem solvable by an exact two way QFA in exponential expected time but not by any bounded error sublogarithmic space probabilistic Turing machine (PTM). There is a promise problem solvable by an exact two way QFA in quadratic expected time but not by any bounded error o(loglogn) space PTMs in polynomial expected time. The same problem can be solvable by a one way Las Vegas (or exact two way) QFA with quantum head in linear (expected) time. There is a promise problem solvable by a Las …

Amount of Nonconstructivity in Finite Automata

2009

When D. Hilbert used nonconstructive methods in his famous paper on invariants (1888), P.Gordan tried to prevent the publication of this paper considering these methods as non-mathematical. L. E. J. Brouwer in the early twentieth century initiated intuitionist movement in mathematics. His slogan was "nonconstructive arguments have no value for mathematics". However, P. Erdos got many exciting results in discrete mathematics by nonconstructive methods. It is widely believed that these results either cannot be proved by constructive methods or the proofs would have been prohibitively complicated. R.Freivalds [7] showed that nonconstructive methods in coding theory are related to the notion of…

The existence of best proximity points in metric spaces with the property UC

2009

Abstract Eldred and Veeramani in [A.A. Eldred, P. Veeramani, Existence and convergence of best proximity points, J. Math. Anal. Appl., 323 (2006), 1001–1006. MR2260159] proved a theorem which ensures the existence of a best proximity point of cyclic contractions in the framework of uniformly convex Banach spaces. In this paper we introduce a notion of the property UC and extend the Eldred and Veeramani theorem to metric spaces with the property UC.

Indecomposable modules over the Virasoro Lie algebra and a conjecture of V. Kac

1991

We consider a class of indecomposable modules over the Virasoro Lie algebra that we call bounded admissible modules. We get results concerning the center and the dimensions of the weight spaces. We prove that these modules always contain a submodule with one-dimensional weight spaces. From this follows the proof of a conjecture of V. Kac concerning the classification of simple admissible modules.

Slopes of Non-hyperelliptic Fibrations in Positive Characteristic

2016

Maximal function estimates and self-improvement results for Poincaré inequalities

2018

Our main result is an estimate for a sharp maximal function, which implies a Keith–Zhong type self-improvement property of Poincaré inequalities related to differentiable structures on metric measure spaces. As an application, we give structure independent representation for Sobolev norms and universality results for Sobolev spaces. peerReviewed

On the regularity of the partial {$O\sp *$}-algebras generated by a closed symmetric operator

1992

Let be given a dense domain D in a Hilbert space and a closed symmetric operator T with domain containing D. Then the restriction of T to D generates (algebraically) two partial *-algebras of closable operators (called weak and strong), possibly nonabelian and nonassociative. We characterize them completely. In particular, we examine under what conditions they are regular, that is, consist of polynomials only, and standard. Simple differential operators provide concrete examples of all the pathologies allowed by the abstract theory.