摘要:

AbstractThe descriptive complexity of a problem is the complexity of describing the problem in some logical formalism. One of the few techniques for proving separation results in descriptive complexity is to make use of games on graphs played between two players, called the spoiler and the duplicator. There are two types of these games, which differ in the order in which the spoiler and duplicator make various moves. In one of these games, the rules seem to be tilted towards favoring the duplicator. These seemingly more favorable rules make it easier to prove separation results, since separation results are proven by showing that the duplicator has a winning strategy. In this paper, the relationship between these games is investigated. It is shown that in one sense, the two games are equivalent. Specifically, each family of graphs used in one game (the game with the seemingly more favorable rules for the duplicator) to prove a separation result can in principle be used in the other game to prove the same result. This answers an open question of Ajtai and the author from 1989. It is also shown that in another sense, the games are not equivalent, in that there are situations where the spoiler requires strictly more resources to win one game than the other game. This makes formal the informal statement that one game is easier for the duplicator to win.

ISSN:0942-5616    

DOI:10.1002/malq.19970430402

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1997

数据来源: WILEY

摘要:

AbstractIt is shown that if (M,<, ⃛) is an o‐minimal structure such that (M,<) is a dense total order and ≾ is a parameter‐definable partial order onM, then ≾ has an extension to a definable to

ISSN:0942-5616    

DOI:10.1002/malq.19970430403

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1997

数据来源: WILEY

摘要:

AbstractThis is a study of the set of the Malitz‐completions (which are a special case of Cauchy‐completions) of a given infinite first‐order structure, put in relation with properties of directed

ISSN:0942-5616    

DOI:10.1002/malq.19970430404

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1997

数据来源: WILEY

摘要:

AbstractKripke bundle and C‐set semantics are known as semantics which generalize standard Kripke semantics. In [4] and in [1, 2]it is shown that Kripke bundle and C‐set semantics are stronger than standard Kripke semantics. Also it is true that C‐set semantics for superintuitionistic logics is stronger than Kripke bundle semantics ([6]). Modal predicate logic Q‐S4.1 is not Kripke bundle complete ([3]‐ it is also yielded as a corollary to Theorem 6.1(a) of the present paper). This is shown by using difference of Kripke bundle semantics and C‐set semantics. In this paper, by using the same idea we show that incompleteness results in Kripke bundle semantics which are extended vers

ISSN:0942-5616    

DOI:10.1002/malq.19970430405

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1997

数据来源: WILEY

摘要:

AbstractWe give a rough statement of the main result. LetDbe a compact subset of ℝ3× ℝ. The propagationu(x, y, z, t) of a wave can be noncomputablein any neighborhoodof any point ofDeven though the initial conditions which determine the wave propagation uniquely are computable. A precise statement of the result appears b

ISSN:0942-5616    

DOI:10.1002/malq.19970430406

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1997

数据来源: WILEY

摘要:

AbstractWe describe sets of partial Boolean functions being closed under the operations of superposition. For any classAof total functions we define the set

ISSN:0942-5616    

DOI:10.1002/malq.19970430407

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1997

数据来源: WILEY

摘要:

AbstractWe give some information about the action of Aut(M) on M(0), where M is a countable arithmetically saturated model of Peano Arithmetic. We concentrate on analogues of moving gaps and covering gaps inside M(0).

ISSN:0942-5616    

DOI:10.1002/malq.19970430408

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1997

数据来源: WILEY

摘要:

AbstractWe study the distributivity of the bounded ideal onPkλ and answer negatively to a question of Johnson in [13]. The size of non‐normal ideals with the partition property is also studi

ISSN:0942-5616    

DOI:10.1002/malq.19970430409

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1997

数据来源: WILEY

摘要:

AbstractThe language of the propositional calculus is extended by two families of propositional probability operators, inductively applicable to the formulae, and the set of all formulae provable in an arbitrary superintuitionistic propositional logic is extended by the probability measure axioms concerning those probability operators. A logical system obtained in such a way, similar to a kind of polymodal logic, makes possible to express a probability measure of truthfulness of any formula. The paper contains a description of the Kripke‐type possible worlds semantics covering the considered logical systems, being followed by the corresponding completeness result

ISSN:0942-5616    

DOI:10.1002/malq.19970430410

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1997

数据来源: WILEY

摘要:

AbstractWe consider the strongest (most restricted) forms of enumeration reducibility, those that occur between 1‐ and npm‐reducibility inclusive. By defining two new reducibilities (which we call n1‐ and ni‐reducibility) which are counterparts to 1‐ and i‐reducibility, respectively, in the same way that nm‐ and npm‐reducibility are counterparts to m‐ and pm‐reducibility, respectively, we bring out the structure (under the natural relation on reducibilities strong with respect to') of the strong reducibilities. By further restricting n1‐ and nm‐reducibility we are able to define infinite families of reducibilities which isomorphically embed the r. e. Turing degrees. Thus the many well‐known results in the theory of the r. e. Turing degrees have counterparts in the theory of strong reducibilities. We are also able to positively answer the question of whether there exist distinct reducibilities ≤yand ≤abetween ≤eand ≤msuch that there exists a n

ISSN:0942-5616    

DOI:10.1002/malq.19970430411

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1997

数据来源: WILEY