摘要:

AbstractWe show that derivations in the nonassociative and commutative Lambek calculus with product can be transformed to a normal form as it is the case with derivations in noncommutative calculi. As an application we obtain that the class of languages generated by categorial grammars based on the nonassociative and commutative Lambek calculus with product is included in the class of CF‐languages. MSC: 68Q50, 03D15, 03B6

ISSN:0942-5616    

DOI:10.1002/malq.19930390113

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1993

数据来源: WILEY

摘要:

AbstractThe problem of Common Knowledge will be considered in two classes of models: a classK.* of Kripke models and a classSof Scott models. Two modal logic systems will be defined. Those systems, KC and MC, include an axiomatisation of Common Knowledge. We prove determination of each system by the corresponding class of models. MSC: 03B45, 68T25.

ISSN:0942-5616    

DOI:10.1002/malq.19930390114

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1993

数据来源: WILEY

摘要:

AbstractThe uniqueness of the parallel lines is independent from the analogous statement on parallel planes and the usual further axioms of three‐dimensional affine geometry. MSC: 51A15, 03F6

ISSN:0942-5616    

DOI:10.1002/malq.19930390115

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1993

数据来源: WILEY

摘要:

AbstractSambin [6] proved the normalization theorem (Hauptsatz) for GL, the modal logic of provability, in a sequent calculus version called by him GLS. His proof does not take into account the concept of reduction, commonly used in normalization proofs. Bellini [1], on the other hand, gave a normalization proof for GL using reductions. Indeed, Sambin's proof is a decision procedure which builds cut‐free proofs. In this work we formalize this procedure as a recursive function and prove its recursiveness in an arithmetically formalizable way, concluding that the normalization of GL can be formalized in PA. MSC: 03F05, 03B35, 03B4

ISSN:0942-5616    

DOI:10.1002/malq.19930390116

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1993

数据来源: WILEY

摘要:

AbstractA pseudo‐natural algorithm for the word problem of a finitely presented group is an algorithm which not only tells us whether or not a wordwequals 1 in the group but also gives a derivation of 1 fromwwhenwequals 1. In [13], [14]Madlener and Otto show that, if we measure complexity of a primitive recursive algorithm by its level in the Grzegorczyk hierarchy, there are groups in which a pseudo‐natural algorithm is arbitrarily more complicated than an algorithm which simply solves the word problem. In a given group the lowest degree of complexity that can be realised by a pseudo‐natural algorithm is essentially the derivational complexity of that group. Thus the result separates the derivational complexity of the word problem of a finitely presented group from its intrinsic complexity. The proof given in [13] involves the construction of a finitely presented groupGfrom a Turing machineTsuch that the intrinsic complexity of the word problem forGreflects the complexity of the halting problem ofT, while the derivational complexity of the word problem forGreflects the runtime complexity ofT.The proof of one of the crucial lemmas in [13] is only sketched, and part of the purpose of this paper is to give the full details of this proof. We will also obtain a variant of their proof, using modular machines rather than Turing machines. As for several other results, this simplifies the proofs considerably. MSC: 03D40,

ISSN:0942-5616    

DOI:10.1002/malq.19930390117

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1993

数据来源: WILEY

摘要:

AbstractA cutset ofHis a subset of ∪Hwhich meets every element ofH.Hhas the finite cutset property if every cutset ofHcontains a finite one. We study this notion, and in particular how it is related to the compactness ofHfor the natural topology. MSC: 04A20, 54D3

ISSN:0942-5616    

DOI:10.1002/malq.19930390118

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1993

数据来源: WILEY

摘要:

AbstractA variety of modal logics based on the relevant logicRare presented. Models are given for each of these logics and completeness is shown. It is also shown that each of these logics admits Ackermann's rule γ and as a corollary of this it is proved that each logic is a conservative extension of its counterpart based on classical logic, hence we call them “classically complete”. MSC: 03B45, 0

ISSN:0942-5616    

DOI:10.1002/malq.19930390119

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1993

数据来源: WILEY

摘要:

AbstractWe show that the problem of deciding if a finite set of closed terms in normal form is a basis is recursively unsolvable. The restricted problem concerning one element sets is still recursively unsolvable. MSC: 03B40, 03D35.

ISSN:0942-5616    

DOI:10.1002/malq.19930390120

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1993

数据来源: WILEY

摘要:

AbstractComputable limits and colimits are “recursive counterparts” of the suitable classical concepts from category theory. We present mainly some interesting problems related to computable products. Moreover, some “computable counterparts” of well‐known classical facts from category theory are given. MSC: 03D

ISSN:0942-5616    

DOI:10.1002/malq.19930390121

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1993

数据来源: WILEY

摘要:

AbstractThe present note is a reworking and streamlining of Daigneault and Monk's Representation Theory for Polyadic Algebras. MSC: 03G15.

ISSN:0942-5616    

DOI:10.1002/malq.19930390122

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1993

数据来源: WILEY