A Polynomial-Time Algorithm for Finding Regular Simple Paths in Outerplanar Graphs

Let G be a labeled directed graph with arc labels drawn from alphabet Σ, R be a regular expression over Σ, and x and y be a pair of nodes from G. The regular simple path (RSP) problem is to determine whether there is a simple path p in G from x to y, such that the concatenation of arc labels along p satisfies R. Although RSP is known to be NP-hard in general, we show that it is solvable in polynomial time when G is outerplanar. The proof proceeds by presenting an algorithm which gives a polynomial-time reduction of RSP for outerplanar graphs to RSP for directed acyclic graphs, a problem which has been shown to be solvable in polynomial time.     

Valuations determined by quadratic transforms of a regular ring

Let R be a regular noetherian local ring and let V be the ring of a zero-dimensional valuation v of the quotient field of R dominating R. The aim of this paper is to characterize when V can be obtained from R by the sequence of successive quadratic transforms of R along V. We also show some properties of such valuations in terms of the sequence.     

The double Coxeter arrangement

Let V be Euclidean space. Let be a finite irreducible reflection group. Let be the corresponding Coxeter arrangement. Let S be the algebra of polynomial functions on V. For choose such that . The arrangement is known to be free: the derivation module is a free S-module with generators of degrees equal to the exponents of W. In this paper we prove an analogous theorem for the submodule of defined by . The degrees of the basis elements are all equal to the Coxeter number. The module may be considered a deformation of the derivation module for the Shi arrangement, which is conjectured to be free. The proof is by explicit construction using a derivation introduced by K. Saito in his theory of flat generators. Received: March 13, 1997     

On Certain Isomorphisms between Absolute Galois Groups

Let k be an algebraically closed field of characteristic zero, F be an algebraically closed extension of k of transcendence degree one, and G be the group of automorphisms over k of the field F. The purpose of this note is to calculate the group of continuous automorphisms of G.     

A noncontextualist account of contextualist linguistic data

The paper takes as its starting point the observation that people can be led to retract knowledge claims when presented with previously ignored error possibilities, but offers a noncontextualist explanation of the data. Fallibilist epistemologies are committed to the existence of two kinds of Kp-falsifying contingencies: (i) Non-Ignorable contingencies [NI-contingencies] and (ii) Properly-Ignorable contingencies [PI-contingencies]. For S to know that p, S must be in an epistemic position to rule out all NI-contingencies, but she need not be able to rule out the PI-contingencies. What is required vis-à-vis PI-contingencies is that they all be false. In mentioning PI-contingencies, an interlocutor can lead S mistakenly to think that these contingencies are NI-contingencies, when in fact they are not. Since S cannot rule out these newly mentioned contingencies and since she mistakenly takes them to be NI-contingencies, it is quite natural that she retract her earlier knowledge claim. In short, mentioning NI-contingencies creates a distortion effect. It makes S think that the standards for knowledge are higher than they actually are, which in turn explains why she mistakenly thinks she lacks knowledge. Conclusion: The primary linguistic data offered in support of contextualism can be explained without resorting to contextualism.     

EMBEDDINGS INTO THE CATEGORY OF SUPER UNIFORM SPACES

Abstract

The category US of uniform spaces has been generalised in various ways. The category FUS, of fuzzy uniform spaces and the category GUS, of generalised uniform spaces have both been shown to be good extensions in the sense that US can be embedded into them. We show here that the category SUS, of super uniform spaces also enjoys this property and furthermore, the categories FUS and GUS can be embedded into SUS.     

Multivariate Bernstein and Markov inequalities

For a polynomial P_n of total degree n and a bounded convex set S it will be shown that for 0 < p ∞ with C independent of n and of P_n ε Π_n. The Bernstein inequality will also be generalized and that generalization will be the crucial result. Theorems for higher and mixed derivatives will be achieved.     

On the Kernel of Restriction of Characters*

Let G be a finite group, H be a proper subgroup of G, and S be a unitary subring of C. The kernel of the restriction map S[Irr(G)] → S[Irr(H)] as a ring homomorphism is studied. As a corollary, the main result in [Isaacs, I. M. and Navarro, G., Injective restriction of characters, Arch. Math., 108, 2017, 437–439] is reproved.     

On some nonself mappings

Let X be a Banach space, let K be a non–empty closed subset of X and let T : K → X be a non–self mapping. The main result of this paper is that if T satisfies the contractive–type condition (1.1) below and maps ?K (?K the boundary of K) into K then T has a unique fixed point in K.     

EXCEPTIONAL SEQUENCES FOR QUIVERS OF DYNKIN TYPE

Let kQ be the path algebra of a quiver Q without oriented cycles with n vertices. An indecomposable kQ-module without self-extensions is called exceptional. The braid group B _n with n ? 1 generators acts naturally on the set of complete exceptional sequences. Crawley-Boevey (Proceedings of ICRA VI, Carleton-Ottawa, 1992) and Ringel (Contemp. Math. 1994, 171, 339–352) have pointed out that this action is transitive. The number of complete exceptional sequences for kQ representation finite will be computed here and it is shown to be independent of the orientation of the arrows of the quiver Q. The factor group of the braid group which acts freely on the set of complete exceptional sequences can be regarded as a subgroup of the symmetric group S _{? n} , where ? _n is the number of complete exceptional sequences of the algebra kQ. This group is known for certain special types of quivers. Some other interesting relations of the acting group will be given.     

Regular polygons in taxicab geometry

A polygon of n sides will be called regular in taxicab geometry if it has n equal angles and n sides of equal taxicab length. This paper will show that there are no regular taxicab triangles and no regular taxicab pentagons. The sets of taxicab rectangles and taxicab squares will be shown to be the same, respectively, as the sets of Euclidean rectangles and Euclidean squares. A method of construction for a regular taxicab 2n-gon for any n will be demonstrated.     

General p-valuations on abelian groups

A subgroup of a p-group is valuated in a natural way, and every valuated p-group can be embedded as a valuated subgroup of a p-group. We generalize this theorem to subgroups of p-valuated groups with values in an arbitrary value domain D. The induced valuation on the subgroup assigns to each element an equivalence class of D-valuated rooted trees. In the classical caseD is trivial and the equivalence class of trees can be identified with an extended ordinal. The embedding is functorial if some set-theoretic problems can be overcome, which they can be if D is trivial or equal to the ordinals.     

Simulated factorizations II

Summary A factorization of a finite abelian group is said to be simulated if it is obtained from a factorization into a direct product of subgroups by changing at mostk elements in each subgroup. The question has been asked as to which values ofk imply that in fact at least one subgroup must be left unaltered. This has been shown to be true fork = 1 but to be false, in general, fork = p – 1, wherep is the least prime dividing the order ofG. In this paper it is shown to be true fork = p – 2.     

Fast Construction of Optimal Circulant Preconditioners for Matrices from the Fast Dense Matrix Method

In this paper, we consider solving non-convolution type integral equations by the preconditioned conjugate gradient method. The fast dense matrix method is a fast multiplication scheme that provides a dense discretization matrix A approximating a given integral equation. The dense matrix A can be constructed in O(n) operations and requires only O(n) storage where n is the size of the matrix. Moreover, the matrix-vector multiplication A xcan be done in O(n log n) operations. Thus if the conjugate gradient method is used to solve the discretized system, the cost per iteration is O(n log n) operations. However, for some integral equations, such as the Fredholm integral equations of the first kind, the system will be ill-conditioned and therefore the convergence rate of the method will be slow. In these cases, preconditioning is required to speed up the convergence rate of the method. A good choice of preconditioner is the optimal circulant preconditioner which is the minimizer of C – A _F in Frobenius norm over all circulant matrices C. It can be obtained by taking arithmetic averages of all the entries of A and therefore the cost of constructing the preconditioner is of O(n ²) operations for general dense matrices. In this paper, we develop an O(n log n) method of constructing the preconditioner for dense matrices A obtained from the fast dense matrix method. Application of these ideas to boundary integral equations from potential theory will be given. These equations are ill-conditioned whereas their optimal circulant preconditioned equations will be well-conditioned. The accuracy of the approximation A, the fast construction of the preconditioner and the fast convergence of the preconditioned systems will be illustrated by numerical examples.     

The structure of a kind of connected components with oriented cycles and semi-stable vertices

LetF be an algebraically closed field. A be a finite-dimensional algebra overF,Γ _A be the Auslander-Reiten quiver ofA,Γ be a connected component of Γ _A with oriented cycles and semi-stable vertices and each non-stable vertex In Γ be a projective-injective vertex. The structure of Γ is studied. Projcct supported by Chinese Postdoctor Fund.     

Polynomial preserving maps on certain Jordan algebras

LetB andQ be associative algebras and letS be a Jordan subalgebra ofB. Letf(x ₁,…,x _m ) be a (noncommutative) multilinear polynomial such thatS is closed underf. Letα:S→Q be anf-homomorphism in the sense that it is a linear map preservingf. Under suitable conditions it is shown thatα is essentially given by a ring homomorphism. An analogous theorem forf-derivations is also proved. The proofs rest heavily on results concerning functional identities andd-freeness. The second author was partially supported by a grant from the Ministry of Science of Slovenia.     

Alternatingly Hyperexpansive Operator Tuples

The notion of an alternatingly hyperexpansive operator on a Hilbert space is generalized to that of an alternatingly hyperexpansive operator tuple, which necessitates exploring the theory of absolutely monotone functions as defined on the m-fold product N ^m of the semi-group N of non-negative integers and as defined on semi-open cubes in the m-dimensional real Euclidean space R ^m. The multi-variable Laplace transform and the Stieltjes Moment Problem make a natural appearance in the development of the relevant theory, which also highlights the close connections of alternatingly hyperexpansive operator tuples with completely hyperexpansive and subnormal ones. In particular, if T is subnormal and the joint (Taylor) spectrum of its minimal normal extension is contained in a certain subset of the Hermitian space C ^m, then T turns out to be alternatingly hyperexpansive. In the context of multi-variable weighted shifts, the last assertion can be related to the notion of a Stieltjes Moment Net. The general characterization of an alternatingly hyperexpansive m-variable weighted shift T, however, requires a certain net of (positive) numbers associated with T to be absolutely monotone on N ^m and allows for such a T to be non-subnormal.     

The topology of moduli spaces of group representations: The case of compact surface

Let G be a connected complex semisimple affine algebraic group, and let K be a maximal compact subgroup of G. Let X be a noncompact oriented surface. The main theorem of Florentino and Lawton (2009) [3] says that the moduli space of flat K-connections on X is a strong deformation retraction of the moduli space of flat G-connections on X. We prove that this statement fails whenever X is compact of genus at least two.     

Weak-heap sort

A data structure called aweak-heap is defined by relaxing the requirements for a heap. The structure can be implemented on a 1-dimensional array with one extra bit per data item and can be initialized withn items using exactlyn–1 data element compares. Theoretical analysis and empirical results indicate that it is a competitive structure for sorting. The worst case number of data element comparisons is strictly less than (n–1) logn+0.086013n and the expected number is conjectured to be approximately (n–0.5)logn–0.413n.     

On neighbouring matrices with quadratic elementary divisors

Summary Algorithms are presented which compute theQR factorization of an order-n Toeplitz matrix inO(n ²) operations. The first algorithm computes onlyR explicitly, and the second computes bothQ andR. The algorithms are derived from a well-known procedure for performing the rank-1 update ofQR factors, using the shift-invariance property of the Toeplitz matrix. The algorithms can be used to solve the Toeplitz least-squares problem, and can be modified to solve Toeplitz systems inO(n) space.