On existentially first-order definable languages and their relation to NP
On Existentially First-Order Definable Languages and Their Relation to NP
Under the assumption that the Polynomial-Time Hierarchy does not collapse we show for a regular language L: the unbalanced polynomial-time leaf language class determined by L equals iff L is existentially but not quantifierfree definable in FO[<, min, max, +1, −1]. Furthermore, no such class lies properly between NP and co-1-NP or NP⊕co-NP. The proofs rely on a result of Pin and Weil characterizing the automata of existentially first-order definable languages.
On expandability of models of arithmetic and set theory to models of weak second-order theories
On expansions and extensions of powerful digraphs.
On expansions of weakly o-minimal non-valuational structures by convex predicates
We prove that if ℳ = (M,≤,+,...) is a weakly o-minimal non-valuational structure expanding an ordered group (M,≤,+), then its expansion by a family of "non-valuational" unary predicates remains non-valuational. The paper is based on the author's earlier work on strong cell decomposition for weakly o-minimal non-valuational expansions of ordered groups.
On expansions of β-models
On exposed semigroup homomorphisms.
On extending automorphisms of models of Peano Arithmetic
Continuing the earlier research in [10] we give some information on extending automorphisms of models of PA to end extensions and cofinal extensions.
On extension of the group operation over the Čech-Stone compactification
The convolution of ultrafilters of closed subsets of a normal topological group is considered as a substitute of the extension onto of the group operation. We find a subclass of ultrafilters for which this extension is well-defined and give some examples of pathologies. Next, for a given locally compact group and its dense subgroup , we construct subsets of β algebraically isomorphic to . Finally, we check whether the natural mapping from β onto β is a homomorphism with respect to the extension...
On extension properties for observables
On extensions of Nelson's logic satisfying Dummett's axiom.
On External Properties of Nonstandard Models of Arithmetic
On extremum-searching approximate probabilistic algorithms
On families of Lindelöf and related subspaces of
We consider the families of all subspaces of size ω₁ of (or of a compact zero-dimensional space X of weight ω₁ in general) which are normal, have the Lindelöf property or are closed under limits of convergent ω₁-sequences. Various relations among these families modulo the club filter in are shown to be consistently possible. One of the main tools is dealing with a subspace of the form X ∩ M for an elementary submodel M of size ω₁. Various results with this flavor are obtained. Another tool used...
On families of σ-complete ideals
On fields and ideals connected with notions of forcing
We investigate an algebraic notion of decidability which allows a uniform investigation of a large class of notions of forcing. Among other things, we show how to build σ-fields of sets connected with Laver and Miller notions of forcing and we show that these σ-fields are closed under the Suslin operation.
On ...-filtered vector spaces and their application to abelian p-groups: I.
On fixed edges of antitone self-mappings of complete lattices.
On four intuitionistic fuzzy topological operators.
Four new operators, which are analogous of the topological operators interior and closure, are defined. Some of their basic properties are studied. Their geometrical interpretations are given.
On free Boolean vectors.