Infinitary Action Logic: Complexity, Models and Grammars

Action logic of Pratt [21] can be presented as Full Lambek Calculus FL [14, 17] enriched with Kleene star *; it is equivalent to the equational theory of residuated Kleene algebras (lattices). Some results on axiom systems, complexity and models of this logic were obtained in [4, 3, 18]. Here we prove a stronger form of *-elimination for the logic of *-continuous action lattices and the –completeness of the equational theories of action lattices of subsets of a finite monoid and action lattices of binary relations on a finite universe. We also discuss possible applications in linguistics. Presented by Jacek Malinowski     

The Variety of Lattice Effect Algebras Generated by MV-algebras and the Horizontal Sum of Two 3-element Chains

It has been recently shown [4] that the lattice effect algebras can be treated as a subvariety of the variety of so-called basic algebras. The open problem whether all subdirectly irreducible distributive lattice effect algebras are just subdirectly irreducible MV-chains and the horizontal sum of two 3-element chains is in the paper transferred into a more tractable one. We prove that modulo distributive lattice effect algebras, the variety generated by MV-algebras and is definable by three simple identities and the problem now is to check if these identities are satisfied by all distributive lattice effect algebras or not. Presented by Daniele Mundici     

An Infinitary Extension of Jankov’s Theorem

It is known that for any subdirectly irreducible finite Heyting algebra A and any Heyting algebra B, A is embeddable into a quotient algebra of B, if and only if Jankov’s formula χ _A for A is refuted in B. In this paper, we present an infinitary extension of the above theorem given by Jankov. More precisely, for any cardinal number κ, we present Jankov’s theorem for homomorphisms preserving infinite meets and joins, a class of subdirectly irreducible complete κ-Heyting algebras and κ-infinitary logic, where a κ-Heyting algebra is a Heyting algebra A with # ≥  κ and κ-infinitary logic is the infinitary logic such that for any set Θ of formulas with # Θ ≥  κ, ∨Θ and ∧Θ are well defined formulas.     

Interpolation in computing science: the semantics of modularization

The Interpolation Theorem, first formulated and proved by W. Craig fifty years ago for predicate logic, has been extended to many other logical frameworks and is being applied in several areas of computer science. We give a short overview, and focus on the theory of software systems and modules. An algebra of theories TA is presented, with a nonstandard interpretation of the existential quantifier . In TA, the interpolation property of the underlying logic corresponds with the quantifier combination property . It is shown how the Modularization Theorem, the Factorization Lemma and the Normal Form Theorem for module expressions can be proved in TA. Dedicated to the 50th anniversary of William Craig’s Interpolation Theorem.     

Homogeneous and Universal Dedekind Algebras

A Dedekind algebra is an order pair (B, h) where B is a non-empty set and h is a similarity transformation on B. Each Dedekind algebra can be decomposed into a family of disjoint, countable subalgebras called the configurations of the algebra. There are ₀ isomorphism types of configurations. Each Dedekind algebra is associated with a cardinal-valued function on called its configuration signature. The configuration signature counts the number of configurations in each isomorphism type which occur in the decomposition of the algebra. Two Dedekind algebras are isomorphic iff their configuration signatures are identical. It is shown that configuration signatures can be used to characterize the homogeneous, universal and homogeneous-universal Dedekind algebras. This characterization is used to prove various results about these subclasses of Dedekind algebras.     

MV-Algebras and Quantum Computation

We introduce a generalization of MV algebras motivated by the investigations into the structure of quantum logical gates. After laying down the foundations of the structure theory for such quasi-MV algebras, we show that every quasi-MV algebra is embeddable into the direct product of an MV algebra and a “flat” quasi-MV algebra, and prove a completeness result w.r.t. a standard quasi-MV algebra over the complex numbers. Presented by Heinrich Wansing     

Varieties of Pseudo-Interior Algebras

The notion of a pseudo-interior algebra was introduced by Blok and Pigozzi in [BPIV]. We continue here our studies begun in [BK]. As a consequence of the representation theorem for pseudo-interior algebras given in [BK] we prove that the variety of all pseudo-interior algebras is generated by its finite members. This result together with Jónsson's Theorem for congruence distributive varieties provides a useful technique in the study of the lattice of varieties of pseudo-interior algebras.     

Łukasiewicz-Moisil Relation Algebras

We introduce Łukasiewicz-Moisil relation algebras, obtained by considering a relational dimension over Łukasiewicz-Moisil algebras. We prove some arithmetical properties, provide a characterization in terms of complex algebras, study the connection with relational Post algebras and characterize the simple structures and the matrix relation algebras.     

Weakly higher order cylindric algebras and finite axiomatization of the representables

We show that the variety of n-dimensional weakly higher order cylindric algebras, introduced in Németi [9], [8], is finitely axiomatizable when n > 2. Our result implies that in certain non-well-founded set theories the finitization problem of algebraic logic admits a positive solution; and it shows that this variety is a good candidate for being the cylindric algebra theoretic counterpart of Tarski’s quasi-projective relation algebras. Supported by the Hungarian National Foundation for Scientific Research grant T73601.     

On Fork Arrow Logic and its Expressive Power

We compare fork arrow logic, an extension of arrow logic, and its natural first-order counterpart (the correspondence language) and show that both have the same expressive power. Arrow logic is a modal logic for reasoning about arrow structures, its expressive power is limited to a bounded fragment of first-order logic. Fork arrow logic is obtained by adding to arrow logic the fork modality (related to parallelism and synchronization). As a result, fork arrow logic attains the expressive power of its first-order correspondence language, so both can express the same input–output behavior of processes.     

Semi-DeMorgan algebras

Semi-DeMorgan algebras are a common generalization of DeMorgan algebras and pseudocomplemented distributive lattices. A duality for them is developed that builds on the Priestley duality for distributive lattices. This duality is then used in several applications. The subdirectly irreducible semi-DeMorgan algebras are characterized. A theory of partial diagrams is developed, where properties of algebras are tied to the omission of certain partial diagrams from their duals. This theory is then used to find and give axioms for the largest variety of semi-DeMorgan algebras with the congruence extension property.Semi-deMorgan algebras include demi-p-lattices, the topic of H. Gaitan's contribution to this special edition. D. Hobby's results were obtained independently.     

图式化程度对解决代数文字题的影响

本研究探讨了图式化程度即例子的概括化程度对解决代数文字题的影响。结果表明 :(1 )例子的表层类似性与目标问题具有一种格式塔的同型效应 ,容易解决“属性”一一对应的问题。 (2 )由例子表层类似性构成的图式化程度低 ,迁移的范围比较窄 ;由例子结构类似性构成的图式化程度高 ,适用的范围比较宽。 (3 )尽管增加了例子与目标问题的难度 ,由结构类似性形成的代数图式仍然可以比较容易地解决目标问题     

Priestley Duality for Quasi-Stone Algebras

In this paper we describe the Priestley space of a quasi-Stone algebra and use it to show that the class of finite quasi-Stone algebras has the amalgamation property. We also describe the Priestley space of the free quasi-Stone algebra over a finite set. This revised version was published online in June 2006 with corrections to the Cover Date.     

Representations of monadic <Emphasis Type="Italic">MV</Emphasis> -algebras

Representations of monadic MV -algebra, the characterization of locally finite monadic MV -algebras, with axiomatization of them, definability of non-trivial monadic operators on finitely generated free MV -algebras are given. Moreover, it is shown that finitely generated m-relatively complete subalgebra of finitely generated free MV -algebra is projective.     

Congruences on Dynamic Algebras

The lattice Cong of all dynamic congruences on a given dynamic algebra is presented. Whenever is separable with zero we define dynamic ideal on , given rise to the lattice Ide. The notions of kernel of a dynamic congruence andthe congruence generated by a dynamic ideal are introduced todescribe a Galois connection between Cong and Ide. We study conditions under which a dynamic congruence is determined byits kernel.     

Type Logics and Pregroups

We discuss the logic of pregroups, introduced by Lambek [34], and its connections with other type logics and formal grammars. The paper contains some new ideas and results: the cut-elimination theorem and a normalization theorem for an extended system of this logic, its P-TIME decidability, its interpretation in L1, and a general construction of (preordered) bilinear algebras and pregroups whose universe is an arbitrary monoid. Special Issue Categorial Grammars and Pregroups Edited by Wojciech Buszkowski and Anne Preller     

On the Compositional Extension Problem

A semantics may be compositional and yet partial, in the sense that not all well-formed expressions are assigned meanings by it. Examples come from both natural and formal languages. When can such a semantics be extended to a total one, preserving compositionality? This sort of extension problem was formulated by Hodges, and solved there in a particular case, in which the total extension respects a precise version of the fregean dictum that the meaning of an expression is the contribution it makes to the meanings of complex phrases of which it is a part. Hodges' result presupposes the so-called Husserl property, which says roughly that synonymous expressions must have the same category. Here I solve a different version of the compositional extension problem, corresponding to another type of linguistic situation in which we only have a partial semantics, and without assuming the Husserl property. I also briefly compare Hodges' framework for grammars in terms of partial algebras with more familiar ones, going back to Montague, which use many-sorted algebras instead.

     

Quantum MV algebras

We introduce the notion of quantum MV algebra (QMV algebra) as a generalization of MV algebras and we show that the class of all effects of any Hilbert space gives rise to an example of such a structure. We investigate some properties of QMV algebras and we prove that QMV algebras represent non-idempotent extensions of orthomodular lattices.I should like to thank Prof. M.L. Dalla Chiara and Dr. P. Minari for many interesting comments and remarks. Daniele Mundici     

On subdirectly irreducible OMAs

In this paper some properties of epi-representations and Schmidt-congruence relations of orthomodular partial algebras are investigated and an infinite list of OMA-epi-subdirectly irreducible orthomodular partial algebras will be constructed.Special issue of Studia Logica: Algebraic Theory of Quasivarieties Presented by M. E. Adams, K. V. Adaricheva, W. Dziobiak, and A. V. Kravchenko