2-uniform congruences in majority algebras and a closure operator

A ternary term m(x, y, z) of an algebra is called a majority term if the algebra satisfies the identities m(x, x, y) = x, m(x, y, x) = x and m(y, x, x) = x. A congruence α of a finite algebra is called uniform if all of its blocks (i.e., classes) have the same number of elements. In particular, if all the α-blocks are two-element then α is said to be a 2-uniform congruence. If all congruences of A are uniform then A is said to be a uniform algebra. Answering a problem raised by Gr?tzer, Quackenbush and Schmidt [2], Kaarli [3] has recently proved that uniform finite lattices are congruence permutable. In connection with Kaarli’s result, our main theorem states that for every finite algebra A with a majority term any two 2-uniform congruences of A permute. Examples show that we can say neither “algebra” instead of “algebra with a majority term”, nor “3-uniform” instead of “2-uniform”. Given two nonempty sets A and B, each relation gives rise to a pair of closure operators, which are called the Galois closures on A and B induced by ρ. Galois closures play an important role in many parts of algebra, and they play the main role in formal concept analysis founded by Wille [4]. In order to prove our main theorem, we introduce a pair of smaller closure operators induced by ρ. These closure operators will hopefully find further applications in the future. Dedicated to the memory of Kazimierz Głazek Presented by E. T. Schmidt. Received November 29, 2005; accepted in final form May 23, 2006. This research was partially supported by the NFSR of Hungary (OTKA), grant no. T049433 and T037877.     

An Infinite Presentation of the Torelli Group

In this paper, we construct an infinite presentation of the Torelli subgroup of the mapping class group of a surface whose generators consist of the set of all “separating twists”, all “bounding pair maps”, and all “commutators of simply intersecting pairs” and whose relations all come from a short list of topological configurations of these generators on the surface. Aside from a few obvious ones, all of these relations come from a set of embeddings of groups derived from surface groups into the Torelli group. In the process of analyzing these embeddings, we derive a novel presentation for the fundamental group of a closed surface whose generating set is the set of all simple closed curves.     

External rays to periodic points

We prove that for every polynomial-like holomorphic mapP, ifaεK (filled-in Julia set) and the componentK _aofK containinga is either a point ora is accessible along a continuous curve from the complement ofK andK _ais eventually periodic, thena is accessible along an external ray. Ifa is a repelling or parabolic periodic point, then the set of arguments of the external rays converging toa is a nonempty closed “rotation set”, finite (ifK _ais not a one point) or Cantor minimal containing a pair of arguments of external rays of a critical point in ℂ. In the Appendix we discuss constructions via cutting and glueing, fromP to its external map with a “hedgehog”, and backward. Partially supported by the Edmund Landau Center for Research in Mathematical Analysis, sponsored by the Minerva Foundation (Germany). Supported by the Polish KBN Grants 210469101 “Iteracje i Fraktale” and 210909101 “Uklady Dynamiczne”.     

Sequent calculi for branching time temporal logics of knowledge and beliefwith awareness: Completeness and decidability

In this paper, we consider branching time temporal logic CT L with epistemic modalities for knowledge (belief) and with awareness operators. These logics involve the discrete-time linear temporal logic operators “next” and “until” with the branching temporal logic operator “on all paths”. In addition, the temporal logic of knowledge (belief) contains an indexed set of unary modal operators “agent i knows” (“agent i believes”). In a language of these logics, there are awareness operators. For these logics, we present sequent calculi with a restricted cut rule. Thus, we get proof systems where proof-search becomes decidable. The soundness and completeness for these calculi are proved. Published in Lietuvos Matematikos Rinkinys, Vol. 47, No. 3, pp. 328–340, July–September, 2007.     

Nonlinear Preserver Problems on B（H）

Let H be a complex Hilbert space of dimension greater than 2, and B(H) denote the Banach algebra of all bounded linear operators on H. For A, B ∈ B(H), define the binary relation A ≤* B by A*A = A*B and AA* = AB*. Then (B(H), “≤*”) is a partially ordered set and the relation “≤*” is called the star order on B(H). Denote by Bs(H) the set of all self-adjoint operators in B(H). In this paper, we first characterize nonlinear continuous bijective maps on B _s (H) which preserve the star order in both directions. We characterize also additive maps (or linear maps) on B(H) (or nest algebras) which are multiplicative at some invertible operator.     

Minimization of a functional over the set of causal operators of causal Hilbert space

The minimization problem for a quadratic functional defined on the set of nonwarning (causal) operators acting in a causal Hilbert space can be regarded as an abstrat analog of the Wiener problem on constructing the optimal nonwarning filter. A similar problem also arises in the linear control problem with the quadratic performance criterion (in this case the transfer operators of a closed control system serve as causal ones). The introduction of causal operators in filtering theory and control theory is a mathematical expression of the causality principle, which must be taken into account for a number of problems. In the present paper we attempt to systematize the mathematical foundations of the abstract linear filtering theory, for which its basic results are expressed in terms of operators describing the filtering problem. We introduce and study a class of finite operators, a natural generalization of the class of causal operators, and give a solution of the minimization problem for a quadratic positive functional defined on the set of causal operators acting in a “discrete” causal space. Bibliography: 54 titles. Translated fromProblemy Matematicheskogo Analiza, No. 14, 1995. pp. 143–187.     

Spectrum of operators in ideal spaces

One considers “weighted translation” operators in ideal Banach spaces. It is proved that if the translation is aperiodic (the set of periodic points has measure zero), then the spectrum of such an operator is rotationinvariant. This result can be extended (under certain additional restrictions) to “weighted translation” operators acting in regular subspaces of ideal spaces, in particular, to operators in Hardy spaces. In this note we prove the rotation-invariance of the spectrum of aperiodic operators of “weighted translation” in ideal spaces and uniform B-algebras. Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 65, pp. 196–198, 1976.     

Complementary Sets of Finite Sets

Subsets 𝒜, 𝒮 of an additive group G are complementary if 𝒜 + 𝒮 = G. When 𝒜 is of finite cardinality ∣𝒜∣, and G is ℤ or ℝ, we give sufficient conditions for the existence of a complementary set 𝒮 with “density” not much larger than 1/∣𝒜∣.     

The Geometry of Standard Deontic Logic

Whereas geometrical oppositions (logical squares and hexagons) have been so far investigated in many fields of modal logic (both abstract and applied), the oppositional geometrical side of “deontic logic” (the logic of “obligatory”, “forbidden”, “permitted”, . . .) has rather been neglected. Besides the classical “deontic square” (the deontic counterpart of Aristotle’s “logical square”), some interesting attempts have nevertheless been made to deepen the geometrical investigation of the deontic oppositions: Kalinowski (La logique des normes, PUF, Paris, 1972) has proposed a “deontic hexagon” as being the geometrical representation of standard deontic logic, whereas Joerden (jointly with Hruschka, in Archiv für Rechtsund Sozialphilosophie 73:1, 1987), McNamara (Mind 105:419, 1996) and Wessels (Die gute Samariterin. Zur Struktur der Supererogation, Walter de Gruyter, Berlin, 2002) have proposed some new “deontic polygons” for dealing with conservative extensions of standard deontic logic internalising the concept of “supererogation”. Since 2004 a new formal science of the geometrical oppositions inside logic has appeared, that is “n-opposition theory”, or “NOT”, which relies on the notion of “logical bi-simplex of dimension m” (m = n − 1). This theory has received a complete mathematical foundation in 2008, and since then several extensions. In this paper, by using it, we show that in standard deontic logic there are in fact many more oppositional deontic figures than Kalinowski’s unique “hexagon of norms” (more ones, and more complex ones, geometrically speaking: “deontic squares”, “deontic hexagons”, “deontic cubes”, . . ., “deontic tetraicosahedra”, . . .): the real geometry of the oppositions between deontic modalities is composed by the aforementioned structures (squares, hexagons, cubes, . . ., tetraicosahedra and hyper-tetraicosahedra), whose complete mathematical closure happens in fact to be a “deontic 5-dimensional hyper-tetraicosahedron” (an oppositional very regular solid).      

Form factors,plane partitions,and random walks

An exactly solvable boson model, the so-called “phase model,” is considered. A relation between certain transition matrix elements of this model and boxed plane partitions, three-dimensional Young diagrams placed into a box of finite size, is established, It is shown that the natural model describing the behavior of friendly walkers, ones that can share the same lattice sites, is the “phase model.” An expression for the number of all admissible nests of lattice paths made by a fixed number of friendly walkers for a certain number of steps is obtained. Bibliography 35 titles. Published in Zapiski Nauchnykh Seminarov POMI, Vol. 360, 2008, pp. 5–30.     

Closure Operators and Lattice Extensions

For closure operators Γ and Δ on the same set X, we say that Δ is a weak (resp. strong) extension of Γ if Cl(X, Γ) is a complete meet-subsemilattice (resp. complete sublattice) of Cl(X, Δ). This context is used to describe the extensions of a finite lattice that preserve various properties. This revised version was published online in September 2006 with corrections to the Cover Date.     

The Number of Hierarchical Orderings

An ordered set-partition (or preferential arrangement) of n labeled elements represents a single “hierarchy” these are enumerated by the ordered Bell numbers. In this note we determine the number of “hierarchical orderings” or “societies”, where the n elements are first partitioned into m ≤ n subsets and a hierarchy is specified for each subset. We also consider the unlabeled case, where the ordered Bell numbers are replaced by the composition numbers. If there is only a single hierarchy, we show that the average rank of an element is asymptotic to n/(4 log 2) in the labeled case and to n/4 in the unlabeled case. This revised version was published online in September 2006 with corrections to the Cover Date.     

A proximal method for identifying active manifolds

The minimization of an objective function over a constraint set can often be simplified if the “active manifold” of the constraints set can be correctly identified. In this work we present a simple subproblem, which can be used inside of any (convergent) optimization algorithm, that will identify the active manifold of a “prox-regular partly smooth” constraint set in a finite number of iterations.     

Ordered sets with interval representation and (m,n)-Ferrers relation

Semiorders may form the simplest class of ordered sets with a not necessarily transitive indifference relation. Their generalization has given birth to many other classes of ordered sets, each of them characterized by an interval representation, by the properties of its relations or by forbidden configurations. In this paper, we are interested in preference structures having an interval representation. For this purpose, we propose a general framework which makes use of n-point intervals and allows a systematic analysis of such structures. The case of 3-point intervals shows us that our framework generalizes the classification of Fishburn by defining new structures. Especially we define three classes of ordered sets having a non-transitive indifference relation. A simple generalization of these structures provides three ordered sets that we call “d-weak orders”, “d-interval orders” and “triangle orders”. We prove that these structures have an interval representation. We also establish some links between the relational and the forbidden mode by generalizing the definition of a Ferrers relation.     

Non-embeddable simple relation algebras

This paper presents solutions or partial solutions for several problems in the theory of relation algebras. In a simple relation algebra an element x satisfying the condition (a) must be an atom of . It follows that x must also be an atom in every simple extension of . Andréka, Jónsson and Németi [1, Problem 4] (see [12, Problem P5]) asked whether the converse holds: if x is an atom in every simple extension of a simple relation algebra, must it satisfy (a)? We show that the answer is “no”.? The only known examples of simple relation algebras without simple proper extensions are the algebras of all binary relations on a finite set. Jónsson proposed finding all finite simple relation algebras without simple proper extensions [12, Problem P6]. We show how to construct many new examples of finite simple relation algebras that have no simple proper extensions, thus providing a partial answer for this second problem. These algebras are also integral and nonrepresentable.? Andréka, Jónsson, Németi [1, Problem 2] (see [12, Problem P7]) asked whether there is a countable simple relation algebra that cannot be embedded in a one-generated relation algebra. The answer is “yes”. Givant [3, Problem 9] asked whether there is some k such that every finitely generated simple relation algebra can be embedded in a k-generated simple relation algebra. The answer is “no”. Received November 27, 1996; accepted in final form July 3, 1997.     

Design principles and error analysis for reduced-shear plate-bending finite elements

Summary. In this paper, we consider the problem of designing plate-bending elements which are free of shear locking. This phenomenon is known to afflict several elements for the Reissner-Mindlin plate model when the thickness of the plate is small, due to the inability of the approximating subspaces to satisfy the Kirchhoff constraint. To avoid locking, a “reduction operator” is often applied to the stress, to modify the variational formulation and reduce the effect of this constraint. We investigate the conditions required on such reduction operators to ensure that the approximability and consistency errors are of the right order. A set of sufficient conditions is presented, under which optimal errors can be obtained – these are derived directly, without transforming the problem via a Hemholtz decomposition, or considering it as a mixed method. Our analysis explicitly takes into account boundary layers and their resolution, and we prove, via an asymptotic analysis, that convergence of the finite element approximations will occur uniformly as , even on quasiuniform meshes. The analysis is carried out in the case of a free boundary, where the boundary layer is known to be strong. We also propose and analyze a simple post-processing scheme for the shear stress. Our general theory is used to analyze the well-known MITC elements for the Reissner-Mindlin plate. As we show, the theory makes it possible to analyze both straight and curved elements. We also analyze some other elements. Received June 19, 1995     

An algebraic foundation for factoring linear boundary problems

Motivated by boundary problems for linear differential equations, we define an abstract boundary problem as a pair consisting of a surjective linear map (“differential operator”) and an orthogonally closed subspace of the dual space (“boundary conditions”). Defining the composition of boundary problems corresponding to their Green’s operators in reverse order, we characterize and construct all factorizations of a boundary problem from a given factorization of the defining operator. For the case of ordinary differential equations, the main results can be made algorithmic. We conclude with a factorization of a boundary problem for the wave equation. This work was supported by the Austrian Science Fund (FWF) under the SFB grant F1322.     

Complementary Sets of Finite Sets

Subsets 𝒜, 𝒮 of an additive group G are complementary if 𝒜 + 𝒮 = G. When 𝒜 is of finite cardinality ∣𝒜∣, and G is ℤ or ℝ, we give sufficient conditions for the existence of a complementary set 𝒮 with “density” not much larger than 1/∣𝒜∣. Supported in part by NSF DMS-0074531. Received February 14, 2002; in revised form July 18, 2002 RID="a" ID="a" Dedicated to Professor Edmund Hlawka on the occasion of his 85th birthday     

Conditional lexicographic orders in constraint satisfaction problems

The lexicographically-ordered CSP (“lexicographic CSP” or “LO-CSP” for short) combines a simple representation of preferences with the feasibility constraints of ordinary CSPs. Preferences are defined by a total ordering across all assignments, such that a change in assignment to a given variable is more important than any change in assignment to any less important variable. In this paper, we show how this representation can be extended to handle conditional preferences in two ways. In the first, for each conditional preference relation, the parents have higher priority than the children in the original lexicographic ordering. In the second, the relation between parents and children need not correspond to the importance ordering of variables. In this case, by obviating the “overwhelming advantage” effect with respect to the original variables and values, the representational capacity is significantly enhanced. For problems of the first type, any of the algorithms originally devised for ordinary LO-CSPs can also be used when some of the domain orderings are dependent on assignments to “parent” variables. For problems of the second type, algorithms based on lexical orders can be used if the representation is augmented by variables and constraints that link preference orders to assignments. In addition, the branch-and-bound algorithm originally devised for ordinary LO-CSPs can be extended to handle CSPs with conditional domain orderings.     

A convergent scheme for a non local Hamilton Jacobi equation modelling dislocation dynamics

We study dislocation dynamics with a level set point of view. The model we present here looks at the zero level set of the solution of a non local Hamilton Jacobi equation, as a dislocation in a plane of a crystal. The front has a normal speed, depending on the solution itself. We prove existence and uniqueness for short time in the set of continuous viscosity solutions. We also present a first order finite difference scheme for the corresponding level set formulation of the model. The scheme is based on monotone numerical Hamiltonian, proposed by Osher and Sethian. The non local character of the problem makes it not monotone. We obtain an explicit convergence rate of the approximate solution to the viscosity solution. We finally provide numerical simulations.This work has been supported by funds from ACI JC 1041 “Mouvements d’interfaces avec termes non-locaux”, from ACI-JC 1025 “Dynamique des dislocations” and from ONERA, Office National d’Etudes et de Recherches. The second author was also supported by the ENPC-Région Ile de France.