First-order logic is known to have a severely limited expressive power on finite structures. As a result, several different extensions have been investigated, including fragments of second-order logic, fixpoint logic, and the infinitary logic L∞ωω in which every formula has only a finite number of variables. In this paper, we study generalized quantifiers in the realm of finite structures and combine them with the infinitary logic L∞ωω to obtain the logics L∞ωω, where Q = {Qi: iε I} is a family (...) of generalized quantifiers on finite structures. Using the logics L∞ωω, we can express polynomial-time properties that are not definable in L∞ωω, such as “there is an even number of x” and “there exists at least n/2 x” , without going to second-order logic. We show that equivalence of finite structures relative to L∞ωω can be characterized in terms of certain pebble games that are a variant of the Ehrenfeucht—Fraïssé games. We combine this game-theoretic characterization with sophisticated combinatorial tools from Ramsey theory, such as van der Waerden's Theorem and Folkman's Theorem, in order to investigate the scope and limits of generalized quantifiers in finite model theory. We obtain sharp lower bounds for expressibility in the logics L∞ωω and discover an intrinsic difference between adding finitely many simple unary generalized quantifiers to L∞ωω adding infinitely many. In particular, we show that if Qis a finite sequence of simple unary generalized quantifiers, then the equicardinality, or Härtig, quantifier is not definable in L∞ωω. We also show that the query “does the equivalence relation E have an even number of equivalence classes” is not definable in the extension L∞ωω of L∞ωω by the Härtig quantifier I and any finite sequence Q of simple unary generalized quantifiers. (shrink)

Logical omniscience states that the knowledge set of ordinary rational agents is closed for its logical consequences. Although epistemic logicians in general judge this principle unrealistic, there is no consensus on how it should be restrained. The challenge is conceptual: we must find adequate criteria for separating obvious logical consequences from non-obvious ones. Non-classical game-theoretic semantics has been employed in this discussion with relative success. On the one hand, with urn semantics [15], an expressive fragment of classical game (...) semantics that weakens the dependence relations between quantifiers occurring in a formula, we can formalize, for a broad array of examples, epistemic scenarios in which an individual ignores the validity of some first-order sentence. On the other hand, urn semantics offers a disproportionate restriction of logical omniscience. Therefore, an improvement of this system is needed to obtain a better solution of the problem. In this paper, I argue that our linguistic competence in using quantifiers requires a sort of basic hypothetical logical knowledge that can be formulated as follows: when inquiring after the truth-value of ∀xφ, an individual might be unaware of all substitutional instances this sentence accepts, but at least she must know that, if an element a is given, then ∀xφ holds only if φ is true. This thesis accepts game-theoretic formalization in terms of a refinement of urn semantics. I maintain that the system so obtained affords an improved solution of the logical omniscience problem. To do this, I characterize first-order theoremhood in US+. As a consequence of this result, we will see that the ideal reasoner depicted by US+ only knows the validity of first-order formulas whose Herbrand witnesses can be trivially found, a fact that provides strong evidence that our refinement of urn semantics captures a relevant sense of logical obviousness. (shrink)

Let Mn♯ denote the minimal active iterable extender model which has n Woodin cardinals and contains all reals, if it exists, in which case we denote by Mn the class-sized model obtained by iterating the topmost measure of Mn class-many times. We characterize the sets of reals which are Σ1-definable from R over Mn, under the assumption that projective games on reals are determined:1. for even n, Σ1Mn=⅁RΠn+11;2. for odd n, Σ1Mn=⅁RΣn+11.This generalizes a theorem of Martin and Steel for L, (...) that is, the case n=0. As consequences of the proof, we see that determinacy of all projective games with moves in R is equivalent to the statement that Mn♯ exists for all n∈N, and that determinacy of all projective games of length ω2 with moves in N is equivalent to the statement that Mn♯ exists and satisfies AD for all n∈N. (shrink)

In the dissertation we study the complexity of generalized quantifiers in natural language. Our perspective is interdisciplinary: we combine philosophical insights with theoretical computer science, experimental cognitive science and linguistic theories. -/- In Chapter 1 we argue for identifying a part of meaning, the so-called referential meaning (model-checking), with algorithms. Moreover, we discuss the influence of computational complexity theory on cognitive tasks. We give some arguments to treat as cognitively tractable only those problems which can be computed in polynomial time. (...) Additionally, we suggest that plausible semantic theories of the everyday fragment of natural language can be formulated in the existential fragment of second-order logic. -/- In Chapter 2 we give an overview of the basic notions of generalized quantifier theory, computability theory, and descriptive complexity theory. -/- In Chapter 3 we prove that PTIME quantifiers are closed under iteration, cumulation and resumption. Next, we discuss the NP-completeness of branching quantifiers. Finally, we show that some Ramsey quantifiers define NP-complete classes of finite models while others stay in PTIME. We also give a sufficient condition for a Ramsey quantifier to be computable in polynomial time. -/- In Chapter 4 we investigate the computational complexity of polyadic lifts expressing various readings of reciprocal sentences with quantified antecedents. We show a dichotomy between these readings: the strong reciprocal reading can create NP-complete constructions, while the weak and the intermediate reciprocal readings do not. Additionally, we argue that this difference should be acknowledged in the Strong Meaning hypothesis. -/- In Chapter 5 we study the definability and complexity of the type-shifting approach to collective quantification in natural language. We show that under reasonable complexity assumptions it is not general enough to cover the semantics of all collective quantifiers in natural language. The type-shifting approach cannot lead outside second-order logic and arguably some collective quantifiers are not expressible in second-order logic. As a result, we argue that algebraic (many-sorted) formalisms dealing with collectivity are more plausible than the type-shifting approach. Moreover, we suggest that some collective quantifiers might not be realized in everyday language due to their high computational complexity. Additionally, we introduce the so-called second-order generalized quantifiers to the study of collective semantics. -/- In Chapter 6 we study the statement known as Hintikka's thesis: that the semantics of sentences like ``Most boys and most girls hate each other'' is not expressible by linear formulae and one needs to use branching quantification. We discuss possible readings of such sentences and come to the conclusion that they are expressible by linear formulae, as opposed to what Hintikka states. Next, we propose empirical evidence confirming our theoretical predictions that these sentences are sometimes interpreted by people as having the conjunctional reading. -/- In Chapter 7 we discuss a computational semantics for monadic quantifiers in natural language. We recall that it can be expressed in terms of finite-state and push-down automata. Then we present and criticize the neurological research building on this model. The discussion leads to a new experimental set-up which provides empirical evidence confirming the complexity predictions of the computational model. We show that the differences in reaction time needed for comprehension of sentences with monadic quantifiers are consistent with the complexity differences predicted by the model. -/- In Chapter 8 we discuss some general open questions and possible directions for future research, e.g., using different measures of complexity, involving game-theory and so on. -/- In general, our research explores, from different perspectives, the advantages of identifying meaning with algorithms and applying computational complexity analysis to semantic issues. It shows the fruitfulness of such an abstract computational approach for linguistics and cognitive science. (shrink)

The basic ideas of game-theoretical semantics are implicit in logicians' and mathematicians' folklore but used only sporadically (e.g., game quantifiers, back-and-forth methods, partly ordered quantifiers). the general suggestions of this approach for natural languages are emphasized: the univocity of "is," the failure of compositionality, a reconstruction of aristotelian categories, limitations of generative grammars, unity of sentence and discourse semantics, a new treatment of tenses and other temporal notions, etc.

The paper presents an application of game-theoretical ideas to the semantics of natural language, especially the analysis of quantifiers and anaphora. The paper also introduces the idea of games of imperfect information and connects to partial logics.

Inquisitive first-order logic, InqBQ, is a system which extends classical first-order logic with formulas expressing questions. From a mathematical point of view, formulas in this logic express properties of sets of relational structures. This paper makes two contributions to the study of this logic. First, we describe an Ehrenfeucht–Fraïssé game for InqBQ and show that it characterizes the distinguishing power of the logic. Second, we use the game to study cardinality quantifiers in the inquisitive setting. That is, we (...) study what statements and questions can be expressed in InqBQ about the number of individuals satisfying a given predicate. As special cases, we show that several variants of the question how many individuals satisfy α(x) are not expressible in InqBQ, both in the general case and in restriction to finite models. (shrink)

The superlative quantifiers, at least and at most, are commonly assumed to have the same truth-conditions as the comparative quantifiers more than and fewer than. However, as Geurts & Nouwen have demonstrated, this is wrong, and several theories have been proposed to account for them. In this paper we propose that superlative quantifiers are illocutionary operators; specifically, they modify meta-speech acts.Meta speech-acts are operators that do not express a speech act, but a willingness to make or refrain from making a (...) certain speech act. The classic example is speech act denegation, e.g. I don't promise to come, where the speaker is explicitly refraining from performing the speech act of promising What denegations do is to delimit the future development of conversation, that is, they delimit future admissible speech acts. Hence we call them meta-speech acts. They are not moves in a game, but rather commitments to behave in certain ways in the future. We formalize the notion of meta speech acts as commitment development spaces, which are rooted graphs: The root of the graph describes the commitment development up to the current point in conversation; the continuations from the root describe the admissible future directions.We define and formalize the meta-speech act GRANT, which indicates that the speaker, while not necessarily subscribing to a proposition, refrains from asserting its negation. We propose that superlative quantifiers are quantifiers over GRANTs. Thus, Mary petted at least three rabbits means that the minimal number n such that the speaker GRANTs that Mary petted n rabbits is n = 3. In other words, the speaker denies that Mary petted two, one, or no rabbits, but GRANTs that she petted more.We formalize this interpretation of superlative quantifiers in terms of commitment development spaces, and show how the truth conditions that are derived from it are partly entailed and partly conversationally implicated. We demonstrates how the theory accounts for a wide variety of phenomena regarding the interpretation of superlative quantifiers, their distribution, and the contexts in which they can be embedded. (shrink)

Kripke’s substitutional interpretation of quantifiers is usually said to be unsatisfactory for independence-friendly (IF) languages. The purpose of this paper is to question this claim. Two accounts of substitutional semantics for IF sentences will be written down, and the objection of the so-called ‘dummy variables’ will be ruled out. Moreover, it will be argued, against the traditional view, that Game-Theoretical Semantics (GTS) should be conceived of as substitutional. The paper ends with some remarks concerning the reasons why substitution is (...) especially suitable for dynamic semantics. (shrink)

We add a limited but useful form of quantification to Coalition Logic, a popular formalism for reasoning about cooperation in game-like multi-agent systems. The basic constructs of Quantified Coalition Logic (QCL) allow us to express such properties as "every coalition satisfying property P can achieve φ" and "there exists a coalition C satisfying property P such that C can achieve φ". We give an axiomatisation of QCL, and show that while it is no more expressive than Coalition Logic, it (...) is nevertheless exponentially more succinct. The complexity of QCL model checking for symbolic and explicit state representations is shown to be no worse than that of Coalition Logic, and satisfiability for QCL is shown to be no worse than satisfiability for Coalition Logic. We illustrate the formalism by showing how to succinctly specify such social choice mechanisms as majority voting, which in Coalition Logic require specifications that are exponentially long in the number of agents. (shrink)

We associate the semantic game with chance moves conceived by Blinov with Blamey’s partial logic. We give some equivalent alternatives to the semantic game, some of which are with a third player, borrowing the idea of introducing the pseudo-player called Nature in game theory. We observe that IF propositional logic proposed by Sandu and Pietarinen can be equivalently translated to partial logic, which implies that imperfect information may not be necessary for IF propositional logic. We also indicate (...) that some independent quantifiers can be regarded as dependent quantifiers of indeterminate sequence, using the interjunction connective in partial logic. We conclude our paper by indicating some further research in a more general setting. (shrink)

For every countable wellordering $\alpha $ greater than $\omega $, it is shown that clopen determinacy for games of length $\alpha $ with moves in $\mathbb {N}$ is equivalent to determinacy for a class of shorter games, but with more complicated payoff. In particular, it is shown that clopen determinacy for games of length $\omega ^2$ is equivalent to $\sigma $ -projective determinacy for games of length $\omega $ and that clopen determinacy for games of length $\omega ^3$ is equivalent (...) to determinacy for games of length $\omega ^2$ in the smallest $\sigma $ -algebra on $\mathbb {R}$ containing all open sets and closed under the real game quantifier. (shrink)

The concept of weak emergence is a refinement or specification of the intuitive, general notion of emergence. Basically, a fact about a system is said to be weakly emergent if its holding both (i) is derivable from the fundamental laws of the system together with some set of basic (non-emergent) facts about it, and yet (ii) is only derivable in a particular manner, called “simulation.” This essay analyzes the application of this notion Conway’s Game of Life, and concludes that (...) a modification of the notion would provide a better refinement of the general notion of emergence. It is proposed that emergence be taken as a matter of degree, defined in terms of the amount of simulation required to derive a fact. (shrink)

We add a limited but useful form of quantification to Coalition Logic, a popular formalism for reasoning about cooperation in game-like multi-agent systems. The basic constructs of Quantified Coalition Logic (QCL) allow us to express such properties as “every coalition satisfying property P can achieve φ” and “there exists a coalition C satisfying property P such that C can achieve φ”. We give an axiomatisation of QCL, and show that while it is no more expressive than Coalition Logic, it (...) is nevertheless exponentially more succinct. The complexity of QCL model checking for symbolic and explicit state representations is shown to be no worse than that of Coalition Logic, and satisfiability for QCL is shown to be no worse than satisfiability for Coalition Logic. We illustrate the formalism by showing how to succinctly specify such social choice mechanisms as majority voting, which in Coalition Logic require specifications that are exponentially long in the number of agents. (shrink)

We make a proposal for formalizing simultaneous games at the abstraction level of player’s powers, combining ideas from dynamic logic of sequential games and concurrent dynamic logic. We prove completeness for a new system of ‘concurrent game logic’ CDGL with respect to finite non-determined games. We also show how this system raises new mathematical issues, and throws light on branching quantifiers and independence-friendly evaluation games for first-order logic.

In this paper, we present a prenex form theorem for a version of Independence Friendly logic, a logic with imperfect information. Lifting classical results to such logics turns out not to be straightforward, because independence conditions make the formulas sensitive to signalling phenomena. In particular, nested quantification over the same variable is shown to cause problems. For instance, renaming of bound variables may change the interpretations of a formula, there are only restricted quantifier extraction theorems, and slashed connectives cannot (...) be so easily removed. Thus we correct some claims from Hintikka [8], Caicedo & Krynicki [3] and Hodges [11]. We refine definitions, in particular the notion of equivalence, and sharpen preconditions, allowing us to restore those claims, including the prenex form theorem of Caicedo & Krynicki [3], and, as a side result, we obtain an application to Skolem forms of classical formulas. It is a known fact that a complete calculus for IF-logic is impossible, but with our results we establish several quantifier rules that form a partial calculus of equivalence for a general version of IF-logic reflecting general properties of information flow in games. (shrink)

The sense of agency – the subjective feeling of being in control of our own actions – is one central aspect of the phenomenology of action. Computational models provided important contributions toward unveiling the mechanisms underlying the sense of agency in individual action. In particular, the sense of agency is believed to be related to the match between the actual and predicted consequences of our own actions. In the study of joint action, models are even more necessary to understand the (...) mechanisms underlying the development of coordination strategies and how the subjective experiences of control emerge during the interaction. In a joint action, we not only need to predict the consequences of our own actions; we also need to predict the actions and intentions of our partner, and to integrate these predictions to infer their joint consequences. Understanding our partner and developing mutually satisfactory coordination strategies are key components of joint action and in the development of the sense of joint agency. Here we discuss a computational architecture which addresses the sense of agency during intentional, real-time joint action. We first reformulate previous accounts of the sense of agency in probabilistic terms, as the combination of prior beliefs about the action goals and constraints, and the likelihood of the predicted movement outcomes. To look at the sense of joint agency, we extend classical computational motor control concepts - optimal estimation and optimal control. Regarding estimation, we argue that in joint action the players not only need to predict the consequences of their own actions, but also need to predict partner’s actions and intentions and to integrate these predictions to infer their joint consequences. As regards action selection, we use differential game theory – in which actions develop in continuous space and time - to formulate the problem of establishing a stable form of coordination and as a natural extension of optimal control to joint action. The resulting model posits two concurrent observer-controller loops, accounting for ‘joint’ and ‘self’ action control. The two observers quantify the likelihoods of being in control alone or jointly. Combined with prior beliefs, they provide weighing signals which are used to modulate the ‘joint’ and ‘self’ motor commands. We argue that these signals can be interpreted as the subjective sense of joint and self agency. We demonstrate the model predictions by simulating a sensorimotor interactive task where two players are mechanically coupled and are instructed to perform planar movements to reach a shared final target by crossing two differently located intermediate targets. In particular, we explore the relation between self and joint agency and the information available to each player about their partner. The proposed model provides a coherent picture of the inter-relation of prediction, control, and the sense of agency in a broader range of joint actions. (shrink)

Hintikka’s semantic approach to meaning, a development of Wittgenstein’s view of meaning as use, is the general theme of this chapter. We will focus on the analysis of quantified sentences and on the scope of the principle of compositionality and compare Hintikka’s take on these issues with that of Frege. The aim of this paper is to show that Hintikka’s analysis of quantified expressions as choice functions, in spite of its obvious dissimilarities with respect to the higher-order approach, is actually (...) very close to the Fregean stance on compositionality and context dependence. In particular, we will defend that the Fregean approach to quantifiers is unavoidably linked to the idea that quantified expressions are context-dependent, and therefore should not be conceived under the traditional inside-out model for analysis. (shrink)

We study game formulas the truth of which is determined by a semantical game of uncountable length. The main theme is the study of principles stating reflection of these formulas in various admissible sets. This investigation leads to two weak forms of strict-II11 reflection . We show that admissible sets such as H and Lω2 which fail to have strict-II11 reflection, may or may not, depending on set-theoretic hypotheses satisfy one or both of these weaker forms.

This paper demonstrates the undecidability of a number of logics with quantification over public announcements: arbitrary public announcement logic, group announcement logic, and coalition announcement logic. In APAL we consider the informative consequences of any announcement, in GAL we consider the informative consequences of a group of agents all of which are simultaneously making known announcements. So this is more restrictive than APAL. Finally, CAL is as GAL except that we now quantify over anything the agents not in that group (...) may announce simultaneously as well. The logic CAL therefore has some features of game logic and of ATL. We show that when there are multiple agents in the language, the satisfiability problem is undecidable for APAL, GAL, and CAL. In the single agent case, the satisfiability problem is decidable for all three logics. (shrink)

Gaifman's normal form theorem showed that every first-order sentence of quantifier rank n is equivalent to a Boolean combination of “scattered local sentences”, where the local neighborhoods have radius at most 7n−1. This bound was improved by Lifsches and Shelah to 3×4n−1. We use Ehrenfeucht–Fraïssé type games with a “shrinking horizon” to get a spectrum of normal form theorems of the Gaifman type, depending on the rate of shrinking. This spectrum includes the result of Lifsches and Shelah, with a (...) more easily understood proof and with the bound on the radius improved to 4n−1. We also obtain bounds for a normal form theorem of Schwentick and Barthelmann. (shrink)

We show in this paper that the theory of ordinal addition of any fixed ordinal ωα, with α less than ωω, admits a quantifier elimination. This in particular gives a new proof for the decidability result first established in 1965 by R. Büchi using transfinite automata. Our proof is based on the Ehrenfeucht games, and we show that quantifier elimination go through generalized power.RésuméOn montre ici que, pour tout ordinal α inférieur à ωω, la théorie additive de ωα (...) admet une élimination des quantificateurs. On obtient ainsi une nouvelle preuve de la décidabilité de ces théories . On utilise ici les jeux d'Ehrenfeucht, avec un formalisme à la Ferrante et Rackoff, et on montre que le fait d'admettre une élimination des quantificateurs se transmet par produit généralisé. (shrink)

This paper introduces a new Ehrenfeucht-Fraïssé type game that is played on two classes of models rather than just two models. This game extends and generalizes the known Ajtai-Fagin game to the case when there are several alternating moves played in different models. The game allows Duplicator to delay her choices of the models till the very end of the game, making it easier for her to win. This adds on the toolkit of winning strategies (...) for Duplicator in Ehrenfeucht-Fraïssé type games and opens up new methods for tackling some open problems in descriptive complexity theory. As an application of the class game, it is shown that, if m is a power of a prime, then first order logic augmented with function quantifiers F1n of arity 1 and height n < m can not express that the size of the model is divisible by m. This, together with some new expressibility results for Henkin quantifiers H1n gives some new separation results on the class of finite models among various F1n on one hand and between F1n and H1n on the other. Since function quantifiers involve a bounded type of second order existential quantifiers, the class game solves an open problem raised by Fagin, which asks for some inexpressibility result using a winning strategy by Duplicator in a game that involves more than one coloring round. (shrink)

This volume gathers together essays from some of Hintikka’s colleagues and former students exploring his influence on their work and pursuing some of the insights that we have found in his work. This book includes a comprehensive overview of Hintikka’s philosophy by Dan Kolak and John Symons and an annotated bibliography of Hintikka’s work. Table of Contents: Foreword; Daniel Kolak and John Symons. Hintikka on Epistemological Axiomatizations; Vincent F. Hendricks. Hintikka on the Problem with the Problem of Transworld Identity; Troy (...) Catterson. What is Epistemic Discourse About? Radu J. Bogdan. Interrogative Logic and the Economic Theory of Information; Raymond Dacey. A Metalogical Critique of Wittgensteinian ‘Phenomenology’; William Boos. Theoretical Commensurability By Correspondence Relations: When Empirical Success Implies Theoretical Reference; Gerhard Schurz. What is Abduction?: An Assessment of Jaakko Hintikka's Conception; James H. Fetzer. The dialogic of just being different: Hintikka's new approach to the notion of episteme and its impact on 'second generation' dialogics; Shahid Rahman. Probabilistic Features in Logic Games; Johan F. A. K. van Benthem. On Some Logical Properties of ‘Is True’; Jan Wolenski. The Results are in: The Scope and Import of Hintikka's Philosophy; Daniel Kolak and John Symons. Annotated Bibliography of Jaakko Hintikka. Index. (shrink)

This article proposes an account of knowing-who constructions within a generalisation of Hintikka’s quantified epistemic logic employing the notion of a conceptual cover Aloni PhD thesis [1]. The proposed logical system captures the inherent context-sensitivity of knowing-wh constructions Boër and Lycan, as well as expresses non-trivial cases of so-called concealed questions Heim. Assuming that quantifying into epistemic contexts and knowing-who are linked in the way Hintikka had proposed, the context dependence of the latter will translate into a context dependence of (...) de re attitude ascriptions and this will result in a ready account of a number of traditionally problematic cases including Quine’s well-known double vision puzzles Quine. (shrink)

This paper demonstrates the undecidability of a number of logics with quantification over public announcements: arbitrary public announcement logic, group announcement logic, and coalition announcement logic. In APAL we consider the informative consequences of any announcement, in GAL we consider the informative consequences of a group of agents all of which are simultaneously making known announcements. So this is more restrictive than APAL. Finally, CAL is as GAL except that we now quantify over anything the agents not in that group (...) may announce simultaneously as well. The logic CAL therefore has some features of game logic and of ATL. We show that when there are multiple agents in the language, the satisfiability problem is undecidable for APAL, GAL, and CAL. In the single agent case, the satisfiability problem is decidable for all three logics. (shrink)

We investigate extensions of dependence logic with generalized quantifiers. We also introduce and investigate the notion of a generalized atom. We define a system of semantics that can accommodate variants of dependence logic, possibly extended with generalized quantifiers and generalized atoms, under the same umbrella framework. The semantics is based on pairs of teams, or double teams. We also devise a game-theoretic semantics equivalent to the double team semantics. We make use of the double team semantics by defining a (...) logic $$\hbox {DC}^2$$ DC 2 which canonically fuses together two-variable dependence logic $$\hbox {D}^2$$ D 2 and two-variable logic with counting quantifiers $$\hbox {FOC}^2$$ FOC 2 . We establish that the satisfiability and finite satisfiability problems of $$\hbox {DC}^2$$ DC 2 are complete for $$\hbox {NEXPTIME}$$ NEXPTIME. (shrink)

In this paper we develop an Ehrenfeucht‐Fraïssé game for. Unlike the standard Ehrenfeucht‐Fraïssé games which are modeled solely after the behavior of quantifiers, this new game also takes into account the behavior of connectives in logic. We prove the adequacy theorem for this game. We also apply the new game to prove complexity results about infinite binary strings.

We prove a local normal form theorem of the Gaifman type for the infinitary logic L∞ωω whose formulas involve arbitrary unary quantifiers but finite quantifier rank. We use a local Ehrenfeucht-Fraïssé type game similar to the one in [9]. A consequence is that every sentence of L∞ωω of quantifier rank n is equivalent to an infinite Boolean combination of sentences of the form ψ, where ψ has counting quantifiers restricted to the -neighborhood of y.

Using a variation of the rainbow construction and various pebble and colouring games, we prove that RRA, the class of all representable relation algebras, cannot be axiomatised by any first-order relation algebra theory of bounded quantifier depth. We also prove that the class At(RRA) of atom structures of representable, atomic relation algebras cannot be defined by any set of sentences in the language of RA atom structures that uses only a finite number of variables.

Kovacs argues that honorary authorship and regarding each co-author of multi-authored papers as if they were sole authors when the performance of researchers is being evaluated by their publications mean that we should require authors to identify what proportion of each publication should be attributed to each co-author. Even if such attributions could be made reliably, such a change should not be made. Contributions to authorship cannot be validly quantified, and the relative merits of different publications are also neither equal (...) nor validly quantifiable. Research administrators need to recognise that whatever criteria they adopt to evaluate the performance of researchers, researchers will find a way to game the system in order to maximise their personal benefit. (shrink)