FLQ, the Fastest Quadratic Complexity Bound on the Values of Positive Roots of Polynomials

In this paper we present F LQ, a quadratic complexity bound on the values of the positive roots of polynomials. This bound is an extension of FirstLambda, the corresponding linear complexity bound and, consequently, it is derived from Theorem 3 below. We have implemented FLQ in the Vincent-Akritas-Strzeboński Continued Fractions method (VAS-CF) for the isolation of real roots of polynomials and compared its behavior with that of the theoretically proven best bound, LM Q. Experimental results indicate that whereas F LQ runs on average faster (or quite faster) than LM Q, nonetheless the quality of the bounds computed by both is about the same; moreover, it was revealed that when VAS-CF is run on our benchmark polynomials using F LQ, LM Q and min(F LQ, LM Q) all three versions run equally well and, hence, it is inconclusive which one should be used in the VAS-CF method.

The Interval [0,1] Admits no Functorial Embedding into a Finite-Dimensional or Metrizable Topological Group

An embedding X ⊂ G of a topological space X into a topological group G is called functorial if every homeomorphism of X extends to a continuous group homomorphism of G. It is shown that the interval [0, 1] admits no functorial embedding into a finite-dimensional or metrizable topological group.

Topological Dichotomy and Unconditional Convergence

In this paper, we give a criterion for unconditional convergence with respect to some summability methods, dealing with the topological size of the set of choices of sign providing convergence. We obtain similar results for boundedness. In particular, quasi-sure unconditional convergence implies unconditional convergence.

Isomorphism Problems for the Baire Function Spaces of Topological Spaces

Let a compact Hausdorff space X contain a non-empty perfect subset. If α < β and β is a countable ordinal, then the Banach space Bα (X) of all bounded real-valued functions of Baire class α on X is a proper subspace of the Banach space Bβ (X). In this paper it is shown that: 1. Bα (X) has a representation as C(bα X), where bα X is a compactification of the space P X – the underlying set of X in the Baire topology generated by the Gδ -sets in X. 2. If 1 ≤ α < β ≤ Ω, where Ω is the first uncountable ordinal number, then Bα (X) is uncomplemented as a closed subspace of Bβ (X). These assertions for X = [0, 1] were proved by W. G. Bade [4] and in the case when X contains an uncountable compact metrizable space – by F.K.Dashiell [9]. Our argumentation is one non-metrizable modification of both Bade’s and Dashiell’s methods.

Doitchinov's Construct of Supertopological Spaces is Topological

It is shown that the construct of supertopological spaces and continuous maps is topological.

Regular and Other Kinds of Extensions of Topological Spaces

∗ This work was partially supported by the National Foundation for Scientific Researches at the Bulgarian Ministry of Education and Science under contract no. MM-427/94.

The Point of Continuity Property: Descriptive Complexity and Ordinal Index

∗ Supported by D.G.I.C.Y.T. Project No. PB93-1142

Quasi-Monte Carlo Methods for some Linear Algebra Problems. Convergence and Complexity

We present quasi-Monte Carlo analogs of Monte Carlo methods for some linear algebra problems: solving systems of linear equations, computing extreme eigenvalues, and matrix inversion. Reformulating the problems as solving integral equations with a special kernels and domains permits us to analyze the quasi-Monte Carlo methods with bounds from numerical integration. Standard Monte Carlo methods for integration provide a convergence rate of O(N^(−1/2)) using N samples. Quasi-Monte Carlo methods use quasirandom sequences with the resulting convergence rate for numerical integration as good as O((logN)^k)N^(−1)). We have shown theoretically and through numerical tests that the use of quasirandom sequences improves both the magnitude of the error and the convergence rate of the considered Monte Carlo methods. We also analyze the complexity of considered quasi-Monte Carlo algorithms and compare them to the complexity of the analogous Monte Carlo and deterministic algorithms.

Pseudo-Compact Semi-Topological Groups

Митрофан М. Чобан, Петър Ст. Кендеров, Уорън Б. Муурс - Полу-топологична група (съответно, топологична група) е група, снабдена с топология, относно която груповата оперция произведение е частично непрекъсната по всяка от променливите (съответно, непрекъсната по съвкупност от променливите и обратната операция е също непрекъсната). В настоящата работа ние даваме условия, от топологичен характер, една полу-топологична група да е всъщност топологична група. Например, ние показваме, че всяка сепарабелна псевдокомпактна полу-топологична група е топологична група. Показваме също, че всяка локално псевдокомпактна полу-топологична група, чиято групова операция е непрекъсната по съвкупност от променливите е топологична група.

About Topological Groups and the Baire Property in Remainders

Александър В. Архангелски, Митрофан М. Чобан, Екатерина П. Михайлова - Изследвани са прирасти със свойството на Бер на топологични групи.

On the Time Complexity of the Problem Related to Reducts of Consistent Decision Tables

In recent years, rough set approach computing issues concerning reducts of decision tables have attracted the attention of many researchers. In this paper, we present the time complexity of an algorithm computing reducts of decision tables by relational database approach. Let DS = (U, C ∪ {d}) be a consistent decision table, we say that A ⊆ C is a relative reduct of DS if A contains a reduct of DS. Let s = be a relation schema on the attribute set C ∪ {d}, we say that A ⊆ C is a relative minimal set of the attribute d if A contains a minimal set of d. Let Qd be the family of all relative reducts of DS, and Pd be the family of all relative minimal sets of the attribute d on s. We prove that the problem whether Qd ⊆ Pd is co-NP-complete. However, the problem whether Pd ⊆ Qd is in P .

On Local Uniform Topological Algebras

2000 Mathematics Subject Classification: Primary 46H05, 46H20; Secondary 46M20.