摘要:

AbstractWe investigate the definability in monadic ∑11and monadic Π11of the problems REGk, of whether there is a regular subgraph of degreekin some given graph, and XREGk, of whether, for a given rooted graph, there is a regular subgraph of degreekin which the root has degreek, and their restrictions to graphs in which every vertex has degree at mostk, namely REGkkand XREGkk, respectively, fork≥ 2 (all our graphs are undirected). Our motivation partly stems from the fact (which we prove here) that REGkkand XREGkkare logspace equivalent to CONN and REACH, respectively, fork≥ 3, where CONN is the problem of whether a given graph is connected and REACH is the problem of whether a given graph has a path joining two given vertices. We use monadic first ‐ order reductions, monadic ∑11games and a recent technique due to Fagin, Stockmeyer and Vardi to almost completely classify whether these problems are definable in monadic ∑11and monadic Π11, and we compare the definability of these problems (in monadic ∑11and monadic Π11with their computational complexity (which varies from solvable using logspace t

ISSN:0942-5616    

DOI:10.1002/malq.19970430102

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1997

数据来源: WILEY

摘要:

AbstractWe show that weakly compact cardinals are the smallest large cardinalskwherek+

ISSN:0942-5616    

DOI:10.1002/malq.19970430103

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1997

数据来源: WILEY

摘要:

AbstractIterative characterizations of computable unary functions are useful patterns for the definition of programming languages based on iterative constructs. The features of such a characterization depend on the pairing producing it: this paper offers an infinite class of pairings involving very nice features.

ISSN:0942-5616    

DOI:10.1002/malq.19970430104

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1997

数据来源: WILEY

摘要:

Abstract1. IfAis strongly amorphous (i.e., all relations onAare definable), then its power setP(A)is dually Dedekind infinite, i. e., every function fromP(A)ontoP(A)is injective. 2. The class of “inexhaustible” sets is not closed under supersets unless AC ho

ISSN:0942-5616    

DOI:10.1002/malq.19970430105

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1997

数据来源: WILEY

摘要:

AbstractProductive sets are sets which are “effectively non recursively enumerable”. In the same spirit, we introduce a notion of “effectively nonrecursive sets” and prove an effective version of Post's theorem. We also show that a set is recursively enumerable and effectively nonrecursive in our sense if and only if it is effectively nonrecursive in the sense of Odifre

ISSN:0942-5616    

DOI:10.1002/malq.19970430106

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1997

数据来源: WILEY

摘要:

AbstractWe present a categorical/denotational semantics for the Lambek Syntactic Calculus (LSC), indeed for a λlD‐typed version Curry‐Howard isomorphic to it. The main novelty of our approach is an abstract noncommutative construction with right and left adjoints, called sequential product. It is defined through a hierarchical structure of categories reflecting the implicit permission to sequence expressions and the inductive construction of compound expressions. We claim that Lambek's noncommutative product corresponds to a noncommutative bi‐endofunctor into a category, which encloses all categories of such hierarchical structure. A soundness theorem for LSC is shown with respect to this semantical fra

ISSN:0942-5616    

DOI:10.1002/malq.19970430107

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1997

数据来源: WILEY

摘要:

AbstractWe prove a representation theorem for (abstract) residuated algebras: each residuated algebra is isomorphically embeddable into a powerset residuated algebra. As a consequence, we obtain a completeness theorem for the Generalized Lambek Calculus. We use a Labelled Deductive System which generalizes the one used by Buszkowski [4] and Pankrat'ev [17]in completeness theorems for the Lambek Calculus.

ISSN:0942-5616    

DOI:10.1002/malq.19970430108

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1997

数据来源: WILEY

摘要:

AbstractIn his 1953's paper, Grzegorczyk proved that a certain kind of relation classes of Grzegorczyk's hierarchy could be characterized inductively. We give a simpler version of this characterization.

ISSN:0942-5616    

DOI:10.1002/malq.19970430109

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1997

数据来源: WILEY

摘要:

AbstractIn [5] Phillips proved that one can obtain the additive group of any nonstandard model *ℤ of the ring ℤ of integers by using a linear mod 1 functionh : Fℚ, whereFis the α‐dimensional vector space over ℚ when α is the cardinality of *ℤ. In this connection it arises the question whether there are linear mod 1 functions which are neither addition nor quasi‐linear. We prove that t

ISSN:0942-5616    

DOI:10.1002/malq.19970430110

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1997

数据来源: WILEY

摘要:

AbstractIn this paper we present a collection of results related to the comparability of summands property of regressive isols. We show that if an infinite regressive isol has comparability of summands, then every predecessor of the isol has a weak comparability of summands property. Recently R. Downey proved that there exist regressive isols that are both hyper‐torre and cosimple. There is a surprisingly close connection between non‐recursive recursively enumerable sets and particular retraceable sets and regressive isols. We apply the theorem of Downey to show that among the regressive isols that are related to recursively enumerable sets there are some with a new prope

ISSN:0942-5616    

DOI:10.1002/malq.19970430111

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1997

数据来源: WILEY