Search results for "Continuous"

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.

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.

On certain linear operators in spaces of ultradifferentiable functions

1996

Let ω be a weight in the sense of Braun, Meise, Taylor, which defines a non-quasianalytic class. Let H be a compact subset of ℝn. It is proved that for every function ƒ on ℝn which belongs to the non-quasianalytic (ω)-class, there is an element g of the same class which is analytic on ℝn\H and such that Dαƒ(x) = Dαg(x) for every x ∈ H and α ∈ ℕ0n. A similar result is proved for functions of the Roumieu type. Continuous linear extension operators of Whitney jets with additional properties are also obtained.

Automatic continuity of generalized local linear operators

1980

In this note, we present a general automatic continuity theory for linear mappings between certain topological vector spaces. The theory applies, in particular, to local operators between spaces of functions and distributions, to algebraic homomorphisms between certain topological algebras, and to linear mappings intertwining generalized scalar operators.

Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer

2007

Consider the problem of evaluating an AND-OR formula on an $N$-bit black-box input. We present a bounded-error quantum algorithm that solves this problem in time $N^{1/2+o(1)}$. In particular, approximately balanced formulas can be evaluated in $O(\sqrt{N})$ queries, which is optimal. The idea of the algorithm is to apply phase estimation to a discrete-time quantum walk on a weighted tree whose spectrum encodes the value of the formula.

Transformations by diagonal matrices in a normed space

1962

Group Input Machine

2009

We introduce a new type of internal memory for finite automata and real-time automata. Instead of using tapes with a prescribed Euclidean structure (one-dimensional or two-dimensional tapes) we allow arbitrary group structure of the internal memory of the automata.

Extremal minimality conditions on automata

2012

AbstractIn this paper we investigate the minimality problem of DFAs by varying the set of final states. In other words, we are interested on how the choice of the final states can affect the minimality of the automata. The state-pair graph is a useful tool to investigate such a problem. The choice of a set of final states for the automaton A defines a coloring of the closed components of the state-pair graph and the minimality of A corresponds to a property of these colored components. A particular attention is devoted to the analysis of some extremal cases such as, for example, the automata that are minimal for any choice of the subset of final states F from the state set Q of the automato…

A graph theoretic approach to automata minimality

2012

AbstractThe paper presents a graph-theoretic approach to test the minimality of a deterministic automaton. In particular, we focus on problems concerning the dependence of the minimality of an automaton on the choice of the set F of final states or on the cardinality of the set F. We introduce different minimality conditions of an automaton and show that such conditions can be characterized in graph-theoretic terms.