Although it is known that reachability in undirected finite graphs can be expressed by an existential monadic second-order sentence, our main result is that this is not the case for directed finite graphs (even in the presence of certain "built-in" relations, such as the successor relation). The proof makes use of Ehrenfeucht-Fraisse games, along with probabilistic arguments. However, we show that for directed finite graphs with degree at most k, reachability is expressible by an existential monadic second-order sentence.

The 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 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. (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)

We investigate the definability in monadic ∑11 and monadic Π11 of the problems REGk, of whether there is a regular subgraph of degree k in some given graph, and XREGk, of whether, for a given rooted graph, there is a regular subgraph of degree k in which the root has degree k, and their restrictions to graphs in which every vertex has degree at most k, namely REGkk and XREGkk, respectively, for k ≥ 2 . Our motivation partly stems from (...) the fact that REGkk and XREGkk are logspace equivalent to CONN and REACH, respectively, for k ≥ 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 ∑11 games and a recent technique due to Fagin, Stockmeyer and Vardi to almost completely classify whether these problems are definable in monadic ∑11 and monadic Π11, and we compare the definability of these problems. (shrink)

Reasoning About Knowledge is the first book to provide a general discussion of approaches to reasoning about knowledge and its applications to distributed ...

What is an inference rule? This question does not have a unique answer. One usually finds two distinct standard answers in the literature; validity inference $(\sigma \vdash_\mathrm{v} \varphi$ if for every substitution $\tau$, the validity of $\tau \lbrack\sigma\rbrack$ entails the validity of $\tau\lbrack\varphi\rbrack)$, and truth inference $(\sigma \vdash_\mathrm{t} \varphi$ if for every substitution $\tau$, the truth of $\tau\lbrack\sigma\rbrack$ entails the truth of $\tau\lbrack\varphi\rbrack)$. In this paper we introduce a general semantic framework that allows us to investigate the notion of inference (...) more carefully. Validity inference and truth inference are in some sense the extremal points in our framework. We investigate the relationship between various types of inference in our general framework, and consider the complexity of deciding if an inference rule is sound, in the context of a number of logics of interest: classical propositional logic, a nonstandard propositional logic, various propositional modal logics, and first-order logic. (shrink)

We do a quantitative analysis of modal logic. For example, for each Kripke structure M, we study the least ordinal μ such that for each state of M, the beliefs of up to level μ characterize the agents' beliefs (that is, there is only one way to extend these beliefs to higher levels). As another example, we show the equivalence of three conditions, that on the face of it look quite different, for what it means to say that the agents' (...) beliefs have a countable description, or putting it another way, have a "countable amount of information". The first condition says that the beliefs of the agents are those at a state of a countable Kripke structure. The second condition says that the beliefs of the agents can be described in an infinitary language, where conjunctions of arbitrary countable sets of formulas are allowed. The third condition says that countably many levels of belief are sufficient to capture all of the uncertainty of the agents (along with a technical condition). The fact that all of these conditions are equivalent shows the robustness of the concept of the agents' beliefs having a "countable description". (shrink)

In this paper, I develop a syntactic framework for the analysis ofstrategic form games that is based on a straightforward combination ofstandard systems of doxastic, probabilistic and conditionalpropositional logic. In particular, for the probabilistic part I makeuse of the axiomatization provided in Fagin and Halpern (1994). The use ofconditionals allows to represent a strategic form game by a logicalformula in a very natural way. Also expected utility maximization can benaturally captured. I use this framework to prove a version of (...) a resulton Nash equilibrium conjectures first presented in Aumann and Brandenburger (1995). (shrink)

Empirical research has increasingly turned its attention to distributed cognition. Acts of remembering are embedded in a social, interactional context; cognitive labor is divided between a rememberer and external sources. The present article examines the benefits and costs associated with distributed, collaborative, conversational remembering. Further, we examine the consequences of joint acts of remembering on subsequent individual acts of remembering. Here, we focus on influences on memory through social contagion and socially shared retrieval-induced forgetting. Extending beyond a single social interaction, (...) we consider work that tracks the propagation of socially shared retrieval-induced forgetting throughout larger networks made up of several agents. Although much work has focused on how distributing cognition can augment memory, this is not the primary lesson we draw from the conversational remembering literature. Rather, mnemonic convergence between communicators is a boon to sociality. It allows the formation and maintenance of mnemonic communities, rather than expanding capacity or accuracy of memory per se. (shrink)

Through a phenomenological study of horse-human relations, this article explores the ways in which, as embodied beings, we live relationally, rather than as separate human identities. Conceptually this challenges oppositional logic and humanist assumptions, but where poststructuralist treatments of these issues tend to remain abstract, this article is concerned with an embodied demonstration of the ways in which we experience a relational or in-between logic in our everyday lives.

We argue that pedagogic authority relies on love, which is misunderstood if seen as a matter of actions and subjects. Love is based not on finite subjects and objects existing in Euclidean space and linear time, but, rather, on the non-finite ontology, space and time of relations. Loving authority is a matter of calling and vocation, arising from the spontaneous and simultaneous call-and-response of a lively relation. We make this argument through a reading of Buber’s I–You relation and Murdoch’ s (...) account of the responsiveness of ascetic discipline. In presenting this analysis, we draw upon a case study from a research project on Australian teachers and students. (shrink)

We consider the issue of what an agent or a processor needs to know in order to know that its messages are true. This may be viewed as a first step to a general theory of cooperative communication in distributed systems. An honest message is one that is known to be true when it is sent (or said). If every message that is sent is honest, then of course every message that is sent is true. Various weaker considerations than honesty (...) are investigated with the property that provided every message sent satisfies the condition, then every message sent is true. (shrink)

Prior research suggests brokers do not always act in the best interests of clients, although morally obligated to do so. We empirically investigated this issue focusing on trades executed at best execution price, before and after the introduction of electronic limit-order trading, on the London Stock Exchange. As a result of limit-order trading, the proportion of trades executed at the best execution price for the customer significantly increased. We attribute this to a sustained increase in the liquidity of stocks as (...) a result of limit-order trading, regardless of market capitalisation. We discuss the ethical implications of our findings and conclude that market structures that enhance market competitiveness may help reconcile broker and client interests. (shrink)

This study examined the link between employees’ adult attachment orientations and perceptions of line managers’ interpersonal justice behaviors, and the moderating effect of national culture. Participants from countries categorized as low collectivistic and high collectivistic completed an online survey. Attachment anxiety and avoidance were negatively related to interpersonal justice perceptions. Cultural differences did not moderate the effects of avoidance. However, the relationship between attachment anxiety and interpersonal justice was non-significant in the Southern Asia cultural cluster. Our findings indicate the importance (...) of ‘fit’ between cultural relational values and individual attachment orientations in shaping interpersonal justice perceptions, and highlight the need for more non-western organizational justice research. (shrink)

Abstract In this article we develop a relational understanding of sociality, that is, an account of social life that takes relation as primary. This stands in contrast to the common assumption that relations arise when subjects interact, an account that gives logical priority to separation. We will develop this relational understanding through a reading of the work of Martin Buber, a social philosopher primarily interested in dialogue, meeting, relationship, and the irreducibility and incomparability of reality. In particular, the article contrasts (...) Buber’s work with that of poststructuralist theorists who take as their starting point the deconstruction of the Hegelian logic of binary oppositions. Deconstruction understands difference as the excess that undoes the binary, but Buber, we argue, shows how difference derives from the primacy and ontological undefinability of relation. Relational logic does not exclude the logic of separations and oppositions: relation is the primal ground that makes separations possible. Content Type Journal Article Pages 1-13 DOI 10.1007/s11841-011-0278-9 Authors Andrew Metcalfe, School of Social Sciences and International Studies, University of New South Wales, Sydney, NSW 2052, Australia Ann Game, School of Social Sciences and International Studies, University of New South Wales, Sydney, NSW 2052, Australia Journal Sophia Online ISSN 1873-930X Print ISSN 0038-1527. (shrink)

The mechanisms responsible for the fine tuning of development, where the wildtype phenotype is reproduced with high fidelity, are not well understood. The difficulty in approaching this problem is the identification of mutant phenotypes indicative of a defect in these fine‐tuning control mechanisms. Evolutionary biologists have used asymmetry as a measure of developmental homeostasis. The rationale for this was that, since the same genome controls the development of the left and right sides of a bilaterally symmetrical organism, departures from symmetry (...) can be used to measure genetic or environmental perturbations. This paper examines the relationship between asymmtry and resistance to organophosphorous insecticides in the Australian sheep blowfly, Lucilia cuprina. A resistance gene, Rop‐1, which encodes a carboxylesterase enzyme, also confers a significant increase in asymmetry. Continued exposure of resistant populations to insecticide has selected a dominant suppressor of the asymmetry phenotype. Genetic evidence indicates that the modifier is the L. cuprina Notch homologue. (shrink)