A Cantor series expansion for a real number x with respect to a basic sequence $Q=(q_1,q_2,\dots )$, where $q_i \geq 2$, is a generalization of the base b expansion to an infinite sequence of bases. Ki and Linton in 1994 showed that for ordinary base b expansions the set of normal numbers is a $\boldsymbol {\Pi }^0_3$ -complete set, establishing the exact complexity of this set. In the case of Cantor series there are three natural notions of normality: normality, (...) ratio normality, and distribution normality. These notions are equivalent for base b expansions, but not for more general Cantor series expansions. We show that for any basic sequence the set of distribution normal numbers is $\boldsymbol {\Pi }^0_3$ -complete, and if Q is $1$ -divergent then the sets of normal and ratio normal numbers are $\boldsymbol {\Pi }^0_3$ -complete. We further show that all five non-trivial differences of these sets are $D_2(\boldsymbol {\Pi }^0_3)$ -complete if $\lim _i q_i=\infty $ and Q is $1$ -divergent. This shows that except for the trivial containment that every normal number is ratio normal, these three notions are as independent as possible. (shrink)

In computational complexity theory, decision problems are divided into complexity classes based on the amount of computational resources it takes for algorithms to solve them. In theoretical computer science, it is commonly accepted that only functions for solving problems in the complexity class P, solvable by a deterministic Turing machine in polynomial time, are considered to be tractable. In cognitive science and philosophy, this tractability result has been used to argue that only functions in P can feasibly (...) work as computational models of human cognitive capacities. One interesting area of computational complexity theory is descriptive complexity, which connects the expressive strength of systems of logic with the computational complexity classes. In descriptive complexity theory, it is established that only first-order (classical) systems are connected to P, or one of its subclasses. Consequently, second-order systems of logic are considered to be computationally intractable, and may therefore seem to be unfit to model human cognitive capacities. This would be problematic when we think of the role of logic as the foundations of mathematics. In order to express many important mathematical concepts and systematically prove theorems involving them, we need to have a system of logic stronger than classical first-order logic. But if such a system is considered to be intractable, it means that the logical foundation of mathematics can be prohibitively complex for human cognition. In this paper I will argue, however, that this problem is the result of an unjustified direct use of computational complexity classes in cognitive modelling. Placing my account in the recent literature on the topic, I argue that the problem can be solved by considering computational complexity for humanly relevant problem solving algorithms and input sizes. (shrink)

We say that a first order formula Φ distinguishes a structure M over a vocabulary L from another structure M' over the same vocabulary if Φ is true on M but false on M'. A formula Φ defines an L-structure M if Φ distinguishes M from any other non-isomorphic L-structure M'. A formula Φ identifies an n-element L-structure M if Φ distinguishes M from any other non-isomorphic n-element L-structure M'. We prove that every n-element structure M is identifiable by a (...) formula with quantifier rank less than (1- 1/2k)n+k²-k+4 and at most one quantifier alternation, where k is the maximum relation arity of M. Moreover, if the automorphism group of M contains no transposition of two elements, the same result holds for definability rather than identification. The Bernays-Schönfinkel class consists of prenex formulas in which the existential quantifiers all precede the universal quantifiers. We prove that every n-element structure M is identifiable by a formula in the Bernays-Schönfinkel class with less than (1-1/2k²+2)n+k quantifiers. If in this class of identifying formulas we restrict the number of universal quantifiers to k, then less than n-√ n+k²+k quantifiers suffice to identify M and, as long as we keep the number of universal quantifiers bounded by a constant, at total n-O(√ n) quantifiers are necessary. (shrink)

In this article we review some of the main results of descriptive complexity theory in order to make the reader familiar with the nature of the investigations in this area. We start by presenting the characterization of automata recognizable languages by monadic second-order logic. Afterwards we explain the characterization of various logics by fIxed-point logics. We assume familiarity with logic but try to keep knowledge of complexity theory to aminimum.

Throughout the development of finite model theory, the fragments of first-order logic with only finitely many variables have played a central role. This survey gives an introduction to the theory of finite variable logics and reports on recent progress in the area.For each k ≥ 1 we let Lk be the fragment of first-order logic consisting of all formulas with at most k variables. The logics Lk are the simplest finite-variable logics. Later, we are going to consider infinitary variants and (...) extensions by so-called counting quantifiers.Finite variable logics have mostly been studied on finite structures. Like the whole area of finite model theory, they have interesting model theoretic, complexity theoretic, and combinatorial aspects. For finite structures, first-order logic is often too expressive, since each finite structure can be characterized up to isomorphism by a single first-order sentence, and each class of finite structures that is closed under isomorphism can be characterized by a first-order theory. The finite variable fragments seem to be promising candidates with the right balance between expressive power and weakness for a model theory of finite structures. This may have motivated Poizat [67] to collect some basic model theoretic properties of the Lk. Around the same time Immerman [45] showed that important complexity classes such as polynomial time or polynomial space can be characterized as collections of all classes of finite structures definable by uniform sequences of first-order formulas with a fixed number of variables and varying quantifier-depth. (shrink)

We prove that, for each countable ordinal ξ≥1, there exist some -complete ω-powers, and some -complete ω-powers, extending previous works on the topological complexity of ω-powers [O. Finkel, Topological properties of omega context free languages, Theoretical Computer Science 262 669–697; O. Finkel, Borel hierarchy and omega context free languages, Theoretical Computer Science 290 1385–1405; O. Finkel, An omega-power of a finitary language which is a borel set of infinite rank, Fundamenta informaticae 62 333–342; D. Lecomte, Sur les ensembles de (...) phrases infinies constructibles a partir d’un dictionnaire sur un alphabet fini, Séminaire d’Initiation a l’Analyse, 1, année 2001–2002; D. Lecomte, Omega-powers and descriptive set theory, Journal of Symbolic Logic 70 1210–1232; J. Duparc, O. Finkel, An ω-Power of a Context-Free Language Which Is Borel Above , in: S. Bold, B. Löwe, T. Räsch, J. van Benthem , in the Proceedings of the international conference foundations of the formal sciences V : Infinite Games, November 26th to 29th, 2004, Bonn, Germany, in: Studies in Logic, vol. 11, College Publications at King’s College, 2007, pp. 109–122]. We prove effective versions of these results; in particular, for each recursive ordinal there exist some recursive sets A2<ω such that , where and denote classes of the hyperarithmetical hierarchy. To do this, we prove effective versions of a result by Kuratowski, describing a set as the range of a closed subset of the Baire space ωω by a continuous bijection. This leads us to prove closure properties for the pointclasses in arbitrary recursively presented Polish spaces. We apply our existence results to get better computations of the topological complexity of some sets of dictionaries considered in [D. Lecomte, Omega-powers and descriptive set theory, Journal of Symbolic Logic 70 1210–1232]. (shrink)

Journal of Mathematical Logic, Ahead of Print. Let [math] be an integer. We show that the set of real numbers that are Poisson generic in base [math] is [math]-complete in the Borel hierarchy of subsets of the real line. Furthermore, the set of real numbers that are Borel normal in base [math] and not Poisson generic in base [math] is complete for the class given by the differences between [math] sets. We also show that the effective versions of these results (...) hold in the effective Borel hierarchy. (shrink)

Let [Formula: see text] be an integer. We show that the set of real numbers that are Poisson generic in base [Formula: see text] is [Formula: see text]-complete in the Borel hierarchy of subsets of the real line. Furthermore, the set of real numbers that are Borel normal in base [Formula: see text] and not Poisson generic in base [Formula: see text] is complete for the class given by the differences between [Formula: see text] sets. We also show that the (...) effective versions of these results hold in the effective Borel hierarchy. (shrink)

Let μ be a universal lower enumerable semi-measure . Any computable upper bound for μ can be effectively separated from zero with a constant . Computable positive lower bounds for μ can be nontrivial and allow one to construct natural examples of hypersimple sets.

Descriptive set theory and computability theory are closely-related fields of logic; both are oriented around a notion of descriptive complexity. However, the two fields typically consider objects of very different sizes; computability theory is principally concerned with subsets of the naturals, while descriptive set theory is interested primarily in subsets of the reals. In this paper, we apply a generalization of computability theory, admissible recursion theory, to consider the relative complexity of notions that are of (...) interest in descriptive set theory. In particular, we examine the perfect set property, determinacy, the Baire property, and Lebesgue measurability. We demonstrate that there is a separation of descriptive complexity between the perfect set property and determinacy for analytic sets of reals; we also show that the Baire property and Lebesgue measurability are both equivalent in complexity to the property of simply being a Borel set, for $\boldsymbol {\Sigma ^{1}_{2}}$ sets of reals. (shrink)

Let K denote prefix-free Kolmogorov complexity, and let $K^A$ denote it relative to an oracle A. We show that for any n, $K^{\emptyset ^{(n)}}$ is definable purely in terms of the unrelativized notion K. It was already known that 2-randomness is definable in terms of K (and plain complexity C) as those reals which infinitely often have maximal complexity. We can use our characterization to show that n-randomness is definable purely in terms of K. To do this (...) we extend a certain “limsup” formula from the literature, and apply Symmetry of Information. This extension entails a novel use of semilow sets, and a more precise analysis of the complexity of $\Delta _2^0$ sets of minimal descriptions. (shrink)

The generation of route descriptions is a fundamental task of navigation systems. A particular problem in this context is to identify routes that can easily be described and processed by users. In this work, we present a framework for representing route networks with the qualitative information necessary to evaluate and optimize route descriptions with regard to ambiguities in them. We identify different agent models that differ in how agents are assumed to process route descriptions while navigating through route networks and (...) discuss which agent models can be translated into PDL programs. Further, we analyze the computational complexity of matching route descriptions and paths in route networks in dependency of the agent model. Finally, we empirically evaluate the influence of the agent model on the optimization and the processing of route instructions. (shrink)

Lautemann et al. (1995) gave a descriptive characterisation of the class of context-free languages, showing that a language is context-free iff it is definable as the set of words satisfying some sentence of a particular logic (fragment) over words. The present notes discuss how to specialise this result to the class of linear languages. Somewhat surprisingly, what would seem the most straightforward specialisation actually fails, due to the fact that linear grammars fail to admit a Greibach normal form. We (...) identify an alternative specialisation, based on an alternative characterisation of context-free languages, also noted by Lautemann et al. (1995). (shrink)

Cerebellar Purkinje cells generate two distinct types of spikes, complex and simple spikes, both of which have conventionally been considered to be highly irregular, suggestive of certain types of stochastic processes as underlying mechanisms. Interestingly, however, the interspike interval structures of complex spikes have not been carefully studied so far. We showed in a previous study that simple spike trains are actually composed of regular patterns and single interspike intervals, a mixture that could not be explained by a simple rate-modulated (...) Poisson process. In the present study, we systematically investigated the interspike interval structures of separated complex and simple spike trains recorded in anaesthetized rats, and derived an appropriate stochastic model. We found that: (i) complex spike trains do not exhibit any serial correlations, so they can effectively be generated by a renewal process, (ii) the distribution of intervals between complex spikes exhibits two narrow bands, possibly caused by two oscillatory bands (0.5–1 and 4–8 Hz) in the input to Purkinje cells and (iii) the regularity of regular patterns and single interspike intervals in simple spike trains can be represented by gamma processes of orders, which themselves are drawn from gamma distributions, suggesting that multiple sources modulate the regularity of simple spike trains. (shrink)

We show that if κ is a weakly compact cardinal then the embeddability relation on trees of size κ is invariantly universal. This means that for every analytic quasi-order R on the generalized Cantor space View the MathML source there is an Lκ+κ-sentence φ such that the embeddability relation on its models of size κ, which are all trees, is Borel bi-reducible to R. In particular, this implies that the relation of embeddability on trees of size κ is complete for (...) analytic quasi-orders on View the MathML source. These facts generalize analogous results for κ=ω obtained in Louveau and Rosendal [17] and Friedman and Motto Ros [6], and it also partially extends a result from Baumgartner [3] concerning the structure of the embeddability relation on linear orders of size κ. (shrink)

When philosophers talk about descriptions, usually they have in mind singular definite descriptions such as ‘the finest Greek poet’ or ‘the positive square root of nine’, phrases formed with the definite article ‘the’. English also contains indefinite descriptions such as ‘a fine Greek poet’ or ‘a square root of nine’, phrases formed with the indefinite article ‘a’ (or ‘an’); and demonstrative descriptions (also known as complex demonstratives) such as ‘this Greek poet’ and ‘that tall woman’, formed with the demonstrative articles (...) ‘this’ and ‘that’. Following the custom in philosophy, in this chapter often we use ‘description’ as short for ‘definite description’; and following the custom in linguistics, often we use ‘definite’, ‘indefinite’, and ‘demonstrative’ as shorthand nouns. For the most part we focus on definite and indefinites, although a few words about demonstratives are called for. At the centre of debates about descriptions is the matter of whether they are devices of reference or of predication (simple or higher-order), and much discussion focuses on how various proposals are to be incorporated into broader theories of the semantics of natural language. But philosophical interest goes beyond the confines of linguistics, logic, and the philosophy of language because choices made about the semantics of descriptions have repercussions elsewhere, particularly in epistemology and metaphysics. A simple match of form and meaning appears to fail.1 First, many occurrences of expressions of both forms ‘the φ’ and ‘a φ’ appear to be used to talk about particular individuals. Consider (1). (shrink)

The social intuitionist approach to moral judgments advanced by social psychologist Jonathan Haidt presupposes that it is possible to provide an explanation of the human moral sense without normative implications. By contrast, Iris Murdoch’s philosophical work on moral psychology suggests that every description of morality necessarily involves evaluative features that reveal the thinker’s own moral attitudes and implicit philosophical pictures. In the light of this, we contend that Haidt’s treatment of the story about Julie and Mark, two siblings who decide (...) to have casual, protected, and in his view harmless sex, provides a too simplistic picture of what is involved in understanding human morality. Despite his aim to explain the roots of moral judgments, he fails to provide a deeper understanding of morality in two different respects. First, he does so by suggesting that his story contains all the relevant information needed to take a moral stand on it, and by rejecting as irrelevant the wider human context in which questions about sexual and family relations arise. Second, he simplifies the responses of the people who are subject to his experiment by disregarding their various reasons for disapproving and by equating understanding human morality with explaining an impersonal psychological process. (shrink)

In this paper we deal with the logical description of complexity classes arising in the real number model of computation introduced by Blum, Shub, and Smale [4]. We adapt the approach of descriptive complexity theory for this model developped in [14] and extend it to capture some further complexity classes over the reals by logical means. Among the latter we find NC R , PAR R , EXP R and some others more.

This is a comprehensive discussion of complexity as it arises in physical, chemical, and biological systems, as well as in mathematical models of nature. Common features of these apparently unrelated fields are emphasised and incorporated into a uniform mathematical description, with the support of a large number of detailed examples and illustrations. The quantitative study of complexity is a rapidly developing subject with special impact in the fields of physics, mathematics, information science, and biology. Because of the variety (...) of the approaches, no comprehensive discussion has previously been attempted. This book will be of interest to graduate students and researchers in physics (nonlinear dynamics, fluid dynamics, solid-state, cellular automata, stochastic processes, statistical mechanics and thermodynamics), mathematics (dynamical systems, ergodic and probability theory), information and computer science (coding, information theory and algorithmic complexity), electrical engineering and theoretical biology. (shrink)

The article will be divided into three parts: 1. Explain the literary origins of the nesting pattern and its relationship to cinema narrative, and analyse the nesting tactics commonly used in films under Hollywood’s classical narrative. 2. Describe the variations in nested structures in films made in the 1990s, focusing on self-reflexive nesting, which emerged as a new model beyond conventional nesting during this period. 3. Distinguish the literary style of embedded narratives from the visual recognition mode and provide an (...) example of how the latter is used in films to create impossible puzzles. (shrink)

This fine collection of essays by a leading philosopher of science presents a defence of integrative pluralism as the best description for the complexity of scientific inquiry today. The tendency of some scientists to unify science by reducing all theories to a few fundamental laws of the most basic particles that populate our universe is ill-suited to the biological sciences, which study multi-component, multi-level, evolved complex systems. This integrative pluralism is the most efficient way to understand the different and (...) complex processes - historical and interactive - that generate biological phenomena. This book will be of interest to students and professionals in the philosophy of science. (shrink)

We prove two sets of results concerning computational complexity classes. First, we propose a new variation of the random oracle hypothesis, originally posed by Bennett and Gill after they showed that relative to a randomly chosen oracle, with probability 1. Their original hypothesis was quickly disproven in several ways, most famously in 1992 with the result that, in spite of the classes being shown unequal with probability 1. Here we propose a variation of what it means to be “large” (...) using the Ellentuck topology. In this new context, we demonstrate that the set of oracles separating and is not small, and obtain similar results for the separation of from along with the separation of from. We also show that the set of oracles equating with is large in this new sense. We demonstrate that this version of the hypothesis provides a sufficient condition for unrelativized relationships, at least in the cases considered here. Second, we examine the descriptive complexity of the classes of oracles providing the separations for these various classes, and determine their exact placement in the Borel hierarchy. (shrink)

In this article an epistemological framework is proposed in order to integrate the emergentist thought with systemic studies on biological autonomy, which are focused on the role of organization. Particular attention will be paid to the role of the observer’s activity, especially: (a) the different operations he performs in order to identify the pertinent elements at each descriptive level, and (b) the relationships between the different models he builds from them. According to the approach sustained here, organization will be (...) considered as the result of a specific operation of identification of the relational properties of the functional components of a system, which do not necessarily coincide with the intrinsic properties of its structural constituents. Also, an epistemological notion of emergence—that of “complex emergence”—will be introduced, which can be defined as the insufficiency, even in principle, of a single descriptive modality to provide a complete description of certain classes of systems. This integrative framework will allow us to deal with two issues in biological and emergentist studies: (1) distinguishing the autonomy proper of living systems from some physical processes like those of structural stability and pattern generation, and (2) reconsidering the notion of downward causation not as a direct or indirect influence of the whole on its parts, but instead as an epistemological problem of interaction between descriptive domains in which the concept of organization proposed and the observational operations related to it play a crucial role. (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)

Some demonstrative expressions, those we might term ‘bare demonstratives’, appear without any appended descriptive content (e.g. occurrences of ‘this’ or ‘that’ simpliciter). However, it seems that the majority of demonstrative occurrences do not follow this model. ‘Complex demonstratives’ is the collective term I shall use for phrases formed by adjoining one or more common nouns to a demonstrative expression (e.g. ‘that cat’, ‘this happy man’) and I will call the combination of predicates immediately concatenated with the demonstrative in such (...) phrases the ‘matrix’ of the expression. The question, then, is how we should construe the logical form of such expressions within a semantic theory for our language; and I wish to suggest that some recent answers to this question are, in fact, mistaken. The structure of the paper is as follows: first, I wish to highlight two (often underlying) assumptions about the nature of noun phrases in general, and suggest that, if they are both adopted, they apparently constrain the possible accounts of the logical form of complex demonstratives to just three options. The second and third parts of the paper will be concerned with expanding these options and arguing that none of them are adequate; thus the major part of the paper is concerned with the negative claim that the most obvious moves to make in this area must actually fail on closer inspection. The fourth and final section will then (very briefly) sketch the positive thesis of the paper: that we can deliver a clear and cohesive account of complex demonstratives, armed simply with elements which we will draw from David Kaplan’s theory of demonstratives, but only at the cost of rejecting (or at least refining) one assumption we recognised initially. (shrink)

What is the relationship between complexity in the world and complexity in the mind? Intuitively, increasingly complex objects and events should give rise to increasingly complex mental representations (or perhaps a plateau in complexity after a certain point). However, a counterintuitive possibility with roots in information theory is an inverted U-shaped relationship between the “objective” complexity of some stimulus and the complexity of its mental representation, because excessively complex patterns might be characterized by surprisingly short (...) computational descriptions (e.g., if they are represented as having been generated “randomly”). Here, we demonstrate that this is the case, using a novel approach that takes the notion of “description” literally. Subjects saw static and dynamic visual stimuli whose objective complexity could be carefully manipulated, and they described these stimuli in their own words by giving freeform spoken descriptions of them. Across three experiments totaling over 10,000 speech clips, spoken descriptions of shapes (Experiment 1), dot-arrays (Experiment 2), and dynamic motion-paths (Experiment 3) revealed a striking quadratic relationship between the raw complexity of these stimuli and the length of their spoken descriptions. In other words, the simplest and most complex stimuli received the shortest descriptions, while those stimuli with a “medium” degree of complexity received the longest descriptions. Follow-up analyses explored the particular words used by subjects, allowing us to further explore how such stimuli were represented. We suggest that the mind engages in a kind of lossy compression for overly complex stimuli, and we discuss the utility of such freeform responses for exploring foundational questions about mental representation. (shrink)

We propose a nonmonotonic Description Logic of typicality able to account for the phenomenon of combining prototypical concepts, an open problem in the fields of AI and cognitive modelling. Our logic extends the logic of typicality ALC + TR, based on the notion of rational closure, by inclusions p :: T(C) v D (“we have probability p that typical Cs are Ds”), coming from the distributed semantics of probabilistic Description Logics. Additionally, it embeds a set of cognitive heuristics for concept (...) combination. We show that the complexity of reasoning in our logic is EXPTIME-complete as in ALC. (shrink)

Background Individuals living with multimorbidity and/or mental health issues, low education, socioeconomic status, and polypharmacy are often called complex patients. The complexity of their health and social care needs can make them prone to disease burden and suffering. Therefore, they frequently access health care services to seek guidance for managing their illness and suffering. Aims The aim of this research was to describe the approaches used by nurses to alleviate the suffering of individuals with multimorbidity and complex needs in (...) acute care settings. Research Design A qualitative descriptive approach. Participants and Research Context Semi-structured interviews were conducted with 19 nurses working in general, medical-surgical, specialized, and intensive care settings across five hospitals in Pakistan. Reflexive thematic analysis was used for analysis. Ethical Considerations Ethical approval was obtained from the Ethical Committee of Al-Nafees Medical College Islamabad, Pakistan. Findings Four themes were generated: Deeper Exploration of Patients’ Health-Illness Situation and Complexity, Prioritizing Patient Psychosocial and Emotional Needs, Instilling Hope and Encouragement in Patients, and Creating a Comforting Environment to Foster Sharing of felt needs. Discussion Nurses emphasized the need of deeper inquiry into patients illness situation and complexity to discern the impact of determinants on their well-being and develop care plans that are tailored to address psychosocial, emotional, and physical suffering of this patient population. Conclusions Alleviation of patient suffering is integral to compassionate nursing care. Nurses use a multifaceted approach entailing sensitive understanding, recognizing sociocultural and structural determinants impact on patient situation, and individual and interdisciplinary altruistic actions to alleviate patient suffering. (shrink)

Answering one of the main questions of [S.-D. Friedman, T. Hyttinen and V. Kulikov, Generalized descriptive set theory and classification theory, Mem. Amer. Math. Soc. 230 80, Chap. 7], we show that there is a tight connection between the depth of a classifiable shallow theory [Formula: see text] and the Borel rank of the isomorphism relation [Formula: see text] on its models of size [Formula: see text], for [Formula: see text] any cardinal satisfying [Formula: see text]. This is achieved (...) by establishing a link between said rank and the [Formula: see text]-Scott height of the [Formula: see text]-sized models of [Formula: see text], and yields to the following descriptive set-theoretical analog of Shelah’s Main Gap Theorem: Given a countable complete first-order theory [Formula: see text], either [Formula: see text] is Borel with a countable Borel rank, or it is not Borel at all. The dividing line between the two situations is the same as in Shelah’s theorem, namely that of classifiable shallow theories. We also provide a Borel reducibility version of the above theorem, discuss some limitations to the possible complexities of [Formula: see text], and provide a characterization of categoricity of [Formula: see text] in terms of the descriptive set-theoretical complexity of [Formula: see text]. (shrink)

In a recent book, Jeffrey King (King 2001) argues that complexdemonstratives, i.e., noun phrases of the form `this/that F, are not singular terms. As such,they are not devices of direct reference contributing the referent to the proposition expressed.In this essay I challenge King's position and show how a direct reference view can handle the datahe proposes in favor of the quantificational account. I argue that when a complex demonstrativecannot be interpreted as a singular term, it is best understood as a (...) case of deferredreference – in which case it should be viewed as an anaphora inheriting its value from a quantifiedterm – or as an emphatic description. (shrink)

This article explores the place of complexity science within education and educational research. The discussion begins with the suggestion that educational research has a history of adopting interpretive frames from other domains with little adaptation. Complexity science is argued to compel a different sort of positioning, one that requires accommodation and participation rather than unproblematized assimilation and application. The argument is developed by considering the following simultaneities in education (and) research: knower and knowledge; transphenomenality; transdisciplinarity; interdiscursivity; descriptive (...) and pragmatic insights; representation and presentation; affect and effect; and education and research. (shrink)

In view of the complexity of cyberbullying, this paper aims to address the linguistic and legal aspects of cyberbullying from an interdisciplinary perspective. Based on authentic data collected from real cases, we will expound on features, defining properties and legal remedies of cyberbullying in the countries that contribute to this special issue, such as Nigeria, France, Poland and China. Firstly, we will present an overview of cyberbullying and its definition, along with cyberbullying’s attributes. Next, we will cover the various (...) forms of cyberbullying, such as hate speech, harassment and trolling. Each of these forms of cyberbullying result in numerous outcomes, many of which are serious and, in the worst case, can result in a victim’s death. A discussion of such consequences and the legal remedies for cyberbullying will be provided. On a final note, the contributors seek to enrich the forthcoming studies on cyberbullying by offering suggestions towards descriptive adequacy of cyberbullying. (shrink)

It is argued that complexity is not attributable directly to systems or processes but rather to the descriptions of their `best' models, to reflect their difficulty. Thus it is relative to the modelling language and type of difficulty. This approach to complexity is situated in a model of modelling. Such an approach makes sense of a number of aspects of scientific modelling: complexity is not situated between order and disorder; noise can be explicated by approaches to excess (...) modelling error; and simplicity is not truth indicative but a useful heuristic when models are produced by a being with a tendency to elaborate in the face of error. (shrink)

This summary of the original paradigm of the universal science of complexity starts with the discovered exact origin of the stagnating "end" of conventional, unitary science paradigm and development traditionally presented by its own estimates as the only and the best possible kind of scientific knowledge. Using a transparent generalisation of the exact mathematical formalism of arbitrary interaction process, we show that unitary science approach and description, including its imitations of complexity and chaoticity, correspond to artificial and ultimately (...) strong reduction of the natural plurality of unreduced interaction results called realisations to a single, "average" or "exact", realisation. This severe reduction of the natural world dynamics in unitary science underlies all its unsolvable "mysteries" and "paradoxes", persisting "difficult problems", and finally the modern "end" of the progress of just that, actually very special kind of knowledge, whose irreducible limits lead to the modern deep crisis of the global civilisation development. We show then how the rigorously substantiated restoration of the full richness of real-world dynamics within the intrinsically unified knowledge of the universal science of complexity provides not only the causally complete solution to the old and new problems of unitary science but opens practically unlimited possibilities for the new progress of science and civilisation as a result of this crucial extension, which we call complexity revolution. The unreduced analysis of the universal complexity science shows that at the current critical bifurcation point of development, we have only two incompatible possibilities and emerging tendencies, either the dangerously growing degradation within the dominating unitary science and thinking limits (irrespective of purely empirical technology power becoming even dangerous here) or the new golden age of scientific discoveries and civilisation progress with the qualitatively extended approach and results of unreduced complexity science and the new thinking it implies. (shrink)

Starts by showing that semantic complexity is not as such a barrier to being a referring expression, using the example of compound names. Goes on to consider whether definite descriptions, at least in some uses, should be counted as referring expressions and concludes that they should be, even if one endorses Russellian truth conditions for sentences containing definite descriptions.

We introduce the notion of complexity, first at an intuitive level and then in relatively more concrete terms, explaining the various characteristic features of complex systems with examples. There exists a vast literature on complexity, and our exposition is intended to be an elementary introduction, meant for a broad audience. -/- Briefly, a complex system is one whose description involves a hierarchy of levels, where each level is made of a large number of components interacting among themselves. The (...) time evolution of such a system is of a complex nature, depending on the interactions among subsystems in the next level below the one under consideration and, at the same time, conditioned by the level above, where the latter sets the context for the evolution. Generally speaking, the interactions among the constituents of the various levels lead to a dynamics characterized by numerous characteristic scales, each level having its own set of scales. What is more, a level commonly exhibits ‘emergent properties’ that cannot be derived from considerations relating to its component systems taken in isolation or to those in a different contextual setting. In the dynamic evolution of some particular level, there occurs a self-organized emergence of a higher level and the process is repeated at still higher levels. -/- The interaction and self-organization of the components of a complex system follow the principle commonly expressed by saying that the ‘whole is different from the sum of the parts’. In the case of systems whose behavior can be expressed mathematically in terms of differential equations this means that the interactions are nonlinear in nature. -/- While all of the above features are not universally exhibited by complex systems, these are nevertheless indicative of a broad commonness relative to which individual systems can be described and analyzed. There exist measures of complexity which, once again, are not of universal applicability, being more heuristic than exact. The present state of knowledge and understanding of complex systems is itself an emerging one. Still, a large number of results on various systems can be related to their complex character, making complexity an immensely fertile concept in the study of natural, biological, and social phenomena. -/- All this puts a very definite limitation on the complete description of a complex system as a whole since such a system can be precisely described only contextually, relative to some particular level, where emergent properties rule out an exact description of more than one levels within a common framework. -/- We discuss the implications of these observations in the context of our conception of the so-called noumenal reality that has a mind-independent existence and is perceived by us in the form of the phenomenal reality. The latter is derived from the former by means of our perceptions and interpretations, and our efforts at sorting out and making sense of the bewildering complexity of reality takes the form of incessant processes of inference that lead to theories. Strictly speaking, theories apply to models that are constructed as idealized versions of parts of reality, within which inferences and abstractions can be carried out meaningfully, enabling us to construct the theories. -/- There exists a correspondence between the phenomenal and the noumenal realities in terms of events and their correlations, where these are experienced as the complex behavior of systems or entities of various descriptions. The infinite diversity of behavior of systems in the phenomenal world are explained within specified contexts by theories. The latter are constructs generated in our ceaseless attempts at interpreting the world, and the question arises as to whether these are reflections of `laws of nature' residing in the noumenal world. This is a fundamental concern of scientific realism, within the fold of which there exists a trend towards the assumption that theories express truths about the noumenal reality. We examine this assumption (referred to as a ‘point of view’ in the present essay) closely and indicate that an alternative point of view is also consistent within the broad framework of scientific realism. This is the view that theories are domain-specific and contextual, and that these are arrived at by independent processes of inference and abstractions in the various domains of experience. Theories in contiguous domains of experience dovetail and interpenetrate with one another, and bear the responsibility of correctly explaining our observations within these domains. -/- With accumulating experience, theories get revised and the network of our theories of the world acquires a complex structure, exhibiting a complex evolution. There exists a tendency within the fold of scientific realism of interpreting this complex evolution in rather simple terms, where one assumes (this, again, is a point of view) that theories tend more and more closely to truths about Nature and, what is more, progress towards an all-embracing ‘ultimate theory’ -- a foundational one in respect of all our inquiries into nature. We examine this point of view closely and outline the alternative view -- one broadly consistent with scientific realism -- that there is no ‘ultimate’ law of nature, that theories do not correspond to truths inherent in reality, and that successive revisions in theory do not lead monotonically to some ultimate truth. Instead, the theories generated in succession are incommensurate with each other, testifying to the fact that a theory gives us a perspective view of some part of reality, arrived at contextually. Instead of resembling a monotonically converging series successive theories are analogous to asymptotic series. -/- Before we summarize all the above considerations, we briefly address the issue of the complexity of the {\it human mind} -- one as pervasive as the complexity of Nature at large. The complexity of the mind is related to the complexity of the underlying neuronal organization in the brain, which operates within a larger biological context, its activities being modulated by other physiological systems, notably the one involving a host of chemical messengers. The mind, with no materiality of its own, is nevertheless emergent from the activity of interacting neuronal assemblies in the brain. As in the case of reality at large, there can be no ultimate theory of the mind, from which one can explain and predict the entire spectrum of human behavior, which is an infinitely rich and diverse one. (shrink)

We consider the problem of obtaining logical characterisations of oracle complexity classes. In particular, we consider the complexity classes LOGSPACENP and PTIMENP. For these classes, characterisations are known in terms of NP computable Lindström quantifiers which hold on ordered structures. We show that these characterisations are unlikely to extend to arbitrary structures, since this would imply the collapse of certain exponential complexity hierarchies. We also observe, however, that PTIMENP can be characterised in terms of Lindström quantifers , (...) though it remains open whether this can be done for LOGSPACENP. (shrink)

One of the most important insights that Russell had in presenting his philosophy of language was his view of singular definite descriptions. Russell held that singular phrases of the form ‘the so-and-so’ should not be viewed as names, but rather incomplete symbols which can be said to have meaning only in a context. We should not represent the sentence The inventor of bifocals is bald.as a simple subject-predicate sentence of the form ‘Fa.’ but rather as a complex existential sentence. According (...) to Russell we should analyze as There is a unique x such that x invented bifocals and x is bald.Moreover, if Russell's analysis is correct then the proposition expressed by will be true in a given circumstance provided that there is a unique inventor of bifocals who is bald in that circumstance. (shrink)

This paper critically examines Mitchell’s integrative pluralism. Integrative pluralism is the view that scientific explanations should primarily aim to integrate descriptions from different ontological levels. We contend that, while integrative pluralism is a fundamental strategy in contemporary science, there are specific reasons why one should not expect integration in the sense developed by Mitchell to be the optimal strategy and the one that scientists should always aim for. Drawing on some examples from contemporary biology, we argue that integration is sometimes (...) neither epistemically desirable, nor ontologically achievable. We conclude that integrative pluralism should thus be limited to a specific class of complex systems but cannot be generalised as the preferable research strategy without further information about the epistemic practices of the scientific community or the ontology of the system under investigation. (shrink)