Search results for "CLOSURE"
showing 10 items of 411 documents
Precise bounds for the sequential order of products of some Fréchet topologies
1998
Abstract The sequential order of a topological space is the least ordinal for which the corresponding iteration of the sequential closure is idempotent. Lower estimates for the sequential order of the product of two regular Frechet topologies and upper estimates for the sequential order of the product of two subtransverse topologies are given in terms of their fascicularity and sagittality. It is shown that for every countable ordinal α, there exists a Lasnev topology such that the sequential order of its square is equal to α.
On the Power of Tree-Walking Automata
2000
Tree-walking automata (TWAs) recently received new attention in the fields of formal languages and databases. Towards a better understanding of their expressiveness, we characterize them in terms of transitive closure logic formulas in normal form. It is conjectured by Engelfriet and Hoogeboom that TWAs cannot define all regular tree languages, or equivalently, all of monadic second-order logic. We prove this conjecture for a restricted, but powerful, class of TWAs. In particular, we show that 1-bounded TWAs, that is TWAs that are only allowed to traverse every edge of the input tree at most once in every direction, cannot define all regular languages. We then extend this result to a class …
On the use of relational expressions in the design of efficient algorithms
2005
Relational expressions have finite binary relations as arguments and the operations are composition (·), closure (*), inverse (−1), and union (U). The efficient computation of the relation denoted by a relational expression is considered, and a tight bound is established on the complexity of the algorithm suggested by Hunt, Szymanski and Ullman. The result implies a unified method for deriving efficient algorithms for many problems in parsing. For example, optimal algorithms are derived for strong LL(1) and strong LL(2) parser construction and an efficient polynomialtime algorithm is derived for determining the inessential error entries in an LR(1) parsing table.
On self-normalising subgroups of finite groups
2010
[EN] The aim of this paper is to characterise the classes of groups in which every subnormal subgroup is normal, permutable, or S-permutable by the embedding of the subgroups (respectively, subgroups of prime power order) in their normal, permutable, or S-permutable closure, respectively.
Two-Variable First-Order Logic with Equivalence Closure
2012
We consider the satisfiability and finite satisfiability problems for extensions of the two-variable fragment of first-order logic in which an equivalence closure operator can be applied to a fixed number of binary predicates. We show that the satisfiability problem for two-variable, first-order logic with equivalence closure applied to two binary predicates is in 2-NExpTime, and we obtain a matching lower bound by showing that the satisfiability problem for two-variable first-order logic in the presence of two equivalence relations is 2-NExpTime-hard. The logics in question lack the finite model property; however, we show that the same complexity bounds hold for the corresponding finite sa…
Ordering and Convex Polyominoes
2005
We introduce a partial order on pictures (matrices), denoted by ≼ that extends to two dimensions the subword ordering on words. We investigate properties of special families of discrete sets (corresponding to {0,1}-matrices) with respect to this partial order. In particular we consider the families of polyominoes and convex polyominoes and the family, recently introduced by the authors, of L-convex polyominoes. In the first part of the paper we study the closure properties of such families with respect to the order. In particular we obtain a new characterization of L-convex polyominoes: a discrete set P is a L-convex polyomino if and only if all the elements Q≼P are polyominoes. In the seco…
Fitting classes and lattice formations I
2004
AbstractA lattice formation is a class of groups whose elements are the direct product of Hall subgroups corresponding to pairwise disjoint sets of primes. In this paper Fitting classes with stronger closure properties involving F-subnormal subgroups, for a lattice formation F of full characteristic, are studied. For a subgroup-closed saturated formation G, a characterisation of the G-projectors of finite soluble groups is also obtained. It is inspired by the characterisation of the Carter subgroups as the N-projectors, N being the class of nilpotent groups.
Resolvent Estimates for Non-Selfadjoint Operators via Semigroups
2009
We consider a non-selfadjoint h-pseudodifferential operator P in the semiclassical limit (h → 0). If p is the leading symbol, then under suitable assumptions about the behavior of p at infinity, we know that the resolvent (z–P)–1 is uniformly bounded for z in any compact set not intersecting the closure of the range of p. Under a subellipticity condition, we show that the resolvent extends locally inside the range up to a distance \(\mathcal{O}(1)((h\ln \frac{1}{h})^{k/(k + 1)} )\) from certain boundary points, where \(k \in \{ 2,4, \ldots \} \). This is a slight improvement of a result by Dencker, Zworski, and the author, and it was recently obtained by W. Bordeaux Montrieux in a model sit…
Benzoxetes and Benzothietes ¾ Heterocyclic Analogues of Benzocyclobutene
2012
Benzo-condensed four-ring heterocycles, such as benzoxetes 1 and benzothietes 3 represent multi-purpose starting compounds for the preparation of various higher heterocyclic ring systems. The thermal or photochemical valence isomerizations between the benzenoid forms 1,3 and the higher reactive o-quinoid structures 2,4 provide the basis for the synthetic applications. On the other hand, this valence isomerization impedes in particular the generation and storage of 1 because the thermal equilibrium 1 ⇆ 2 is completely on the side of 2. Thus, the number of erroneous or questionable benzoxete structures published to date is surprisingly high. On the contrary, the thermal equilibrium 3 ⇆ 4 is o…
Towards an integration of individualistic, networked, and institutional approaches to online disclosure and privacy in a networked ecology
2020
In this paper, we review three different approaches to disclosure and privacy: a) an individualistic approach, which emphasizes an individual's control over information access and flow, b) a networked approach focused on information flow in horizontal relations between people, and c) an institutional approach concerned with public and societal privacy risks from platforms, providers, and governments. These approaches co-exist largely independently of each other in privacy and disclosure literature. However, with overlapping public and private spheres of communication where a presumption of individual agency over personal information is no longer tenable, we argue for the importance of bridg…