Search results for "Mathematics::Logic"
showing 10 items of 64 documents
ON TOPOLOGICAL SPACES WITH A UNIQUE QUASI-PROXIMITY
1994
Abstract Trying to solve the question of whether every T 1 topological space with a unique compatible quasi-proximity should be hereditarily compact, we show that it is true for product spaces as well as for locally hereditarily Lindelof spaces.
Countable connected spaces and bunches of arcs in R3
2006
Abstract We investigate the images (also called quotients) of countable connected bunches of arcs in R 3 , obtained by shrinking the arcs to points (see Section 2 for definitions of new terms). First, we give an intrinsic description of such images among T 1 -spaces: they are precisely countable and weakly first countable spaces. Moreover, an image is first countable if and only if it can be represented as a quotient of another bunch with its projection hereditarily quotient (Theorem 2.7). Applying this result we see, for instance, that two classical countable connected T 2 -spaces—the Bing space [R.H. Bing, A connected countable Hausdorff space, Proc. Amer. Math. Soc. 4 (1953) 474], and th…
Graph Connectivity, Monadic NP and built-in relations of moderate degree
1995
It has been conjectured [FSV93] that an existential secondoder formula, in which the second-order quantification is restricted to unary relations (i.e. a Monadic NP formula), cannot express Graph Connectivity even in the presence of arbitrary built-in relations.
Finitary Representations and Images of Transitive Finitary Permutation Groups
1999
Abstract We characterize the point stabilizers and kernels of finitary permutation representations of infinite transitive groups of finitary permutations. Moreover, the number of such representations is determined.
Quantum, stochastic, and pseudo stochastic languages with few states
2014
Stochastic languages are the languages recognized by probabilistic finite automata (PFAs) with cutpoint over the field of real numbers. More general computational models over the same field such as generalized finite automata (GFAs) and quantum finite automata (QFAs) define the same class. In 1963, Rabin proved the set of stochastic languages to be uncountable presenting a single 2-state PFA over the binary alphabet recognizing uncountably many languages depending on the cutpoint. In this paper, we show the same result for unary stochastic languages. Namely, we exhibit a 2-state unary GFA, a 2-state unary QFA, and a family of 3-state unary PFAs recognizing uncountably many languages; all th…
Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations
2010
We present two new quantum algorithms. Our first algorithm is a generalization of amplitude amplification to the case when parts of the quantum algorithm that is being amplified stop at different times. Our second algorithm uses the first algorithm to improve the running time of Harrow et al. algorithm for solving systems of linear equations from O(kappa^2 log N) to O(kappa log^3 kappa log N) where \kappa is the condition number of the system of equations.
The minimal probabilistic and quantum finite automata recognizing uncountably many languages with fixed cutpoints
2019
Discrete Mathematics & Theoretical Computer Science ; vol. 22 no. 1 ; Automata, Logic and Semantics ; 1365-8050
Foundations for the formalization of metamathematics and axiomatizations of consequence theories
2004
Abstract This paper deals with Tarski's first axiomatic presentations of the syntax of deductive system. Andrzej Grzegorczyk's significant results which laid the foundations for the formalization of metalogic, are touched upon briefly. The results relate to Tarski's theory of concatenation, also called the theory of strings, and to Tarski's ideas on the formalization of metamathematics. There is a short mention of author's research in the field. The main part of the paper surveys research on the theory of deductive systems initiated by Tarski, in particular research on (i) the axiomatization of the general notion of consequence operation, (ii) axiom systems for the theories of classic conse…
Conjunction of Conditional Events and t-Norms
2019
We study the relationship between a notion of conjunction among conditional events, introduced in recent papers, and the notion of Frank t-norm. By examining different cases, in the setting of coherence, we show each time that the conjunction coincides with a suitable Frank t-norm. In particular, the conjunction may coincide with the Product t-norm, the Minimum t-norm, and Lukasiewicz t-norm. We show by a counterexample, that the prevision assessments obtained by Lukasiewicz t-norm may be not coherent. Then, we give some conditions of coherence when using Lukasiewicz t-norm
Rapid construction of algebraic axioms from samples
1991
Abstract An axiom is called reliable if it is confirmed in several places in a given sample of algebra. A very effective algorithm for enumerating such axioms is described.