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 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)

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 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.

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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.

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)

Standard semantic theories predict that non-deictic readings for complex demonstratives should be much more widely available than they in fact are. If such readings are the result of a lexical ambiguity, as Kaplan (1977) and others suggest, we should expect them to be available wherever a definite description can be used. The same prediction follows from ‘hidden argument’ theories like the ones described by King (2001) and Elbourne (2005). Wolter (2006), however, has shown that complex demonstratives admit non-deictic interpretations only (...) when a precise set of structural constrains are met. In this paper, I argue that Wolter’s results, properly understood, upend the philosophical status quo. They fatally undermine the ambiguity theory and demand a fundamental rethinking of the hidden argument approach. (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)

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 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)

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)

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)

The philosophical conception of mechanistic explanation is grounded on a limited number of canonical examples. These examples provide an overly narrow view of contemporary scientific practice, because they do not reflect the extent to which the heuristic strategies and descriptive practices that contribute to mechanistic explanation have evolved beyond the well-known methods of decomposition, localization, and pictorial representation. Recent examples from evolutionary robotics and network approaches to biology and neuroscience demonstrate the increasingly important role played by computer simulations and (...) mathematical representations in the epistemic practices of mechanism discovery and mechanism description. These examples also indicate that the scope of mechanistic explanation must be re-examined: With new and increasingly powerful methods of discovery and description comes the possibility of describing mechanisms far more complex than traditionally assumed. (shrink)

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)

Michael Devitt claims that the predicative material that constitutes complex referential expressions makes a semantic contribution to the proposition expressed. He thus deviates from direct referentialism, according to which every referential expression -either simple or complex- contributes just with an object to the proposition expressed, leaving the predicative material out of the semantic content. However, when dealing with misdescriptions, Devitt has suggested a pragmatic way out: the audience can understand what the speaker is referring to even if the object does (...) not fall under the corresponding description. From my perspective, this proposal questions the semantic validity of the predicative material, together with Devitt's original claim. In this paper, I propose a way to solve the problem posed by misdescriptions that appeals to the idea of epistemically relativized properties, according to which the properties ascribed to the object -by means of the predicative material- correspond to the way the speaker thinks of it and not to the way the object really is. Michael Devitt sostiene que el material predicativo que constituye las expresiones referenciales complejas hace un aporte semántico a la proposición expresada, alejándose así del referencialismo directo, para el cual toda expresión referencial -sea ésta simple o compleja- contribuye sólo con un objeto singular a la proposición expresada. Sin embargo, al enfrentarse al problema de las descripciones fallidas, Devitt ofrece una salida pragmática: el oyente comprende a qué se refiere el hablante aun cuando el objeto referido no caiga bajo la descripción utilizada. Esto pone en cuestión la validez semántica del material predicativo, desestimando la postura original de Devitt. En el trabajo propongo una solución a este problema, apelando a la idea de propiedades epistémicamente relativizadas, de acuerdo con la cual lo que se predica del objeto por medio del material predicativo corresponde a las creencias del hablante, y no a lo que el objeto realmente es. (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)

This paper is a systematic investigation of motion expressions in programmatic music description. To address issues with defining the Source MOTION and the Target MUSIC, we utilize Gestalt models (Figure-Ground and Source-Path-Goal) while also critically examining the ontological complexity of the Target MUSIC. We also investigate music motion descriptions considering the role of the describer’s perspective and communicative goals. As previous research has demonstrated, an attentional Goal-bias is common in physical motion description, yet this has been found also to (...) lessen due to audience accommodation effects. We investigate whether this also occurs in music description. Using cognitive linguistic frameworks, we conducted an analysis of 21 English speakers’ written descriptions of dynamic orchestral excerpts. All participants gave a description of one excerpt reporting their own personal experiences and the other excerpt reporting the events of the excerpt for a fictional future participant. We find that addressee accommodation shapes the choice of the ontological types of Figures used from being more subjective and creative in describing music for oneself versus being more objective in describing music for others. However, our investigation does not find sufficient evidence for a Goal-bias in music like there is in physical motion event descriptions. (shrink)

This chapter contains sections titled: Simultaneity 1—Knower and Knowledge Simultaneities 2, 3, and 4—Transphenomenality, Transdisciplinarity, and Interdiscursivity Simultaneity 5—Descriptive and Pragmatic Insights Simultaneity 6—Representation and Presentation Simultaneity 7—Affect and Effect Simultaneity 8—Education and Research A Closing Note on Complicity: The Need for Critical Reflection References.

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)

A model of normative provisions and related axioms represented by using RDF/owl are presented as a contribution to implement the semantic web in the legal domain. In particular, a pattern able to implement the Hohfeldian legal fundamental relations between provisions using OWL-DL expressivity is proposed. Moreover, a query-based approach able to deal with relations between provision instances is described. An example of advanced access and reasoning over provisions using the proposed approach, as well as a prototype architecture of a provision (...) retrieval system, are shown. The main benefit is represented by the ability of the approach to keep the complexity of the problem within a description logic computational tractability. (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)

This paper reexamines some examples, discussed by Mates and others, of sentences containing both definite descriptions and quantifiers. It has frequently been claimed that these sentences provide evidence for the view that definite descriptions themselves are quantifiers. The main goal of this paper is to argue this is not so. Though the examples are compatible with quantificational approaches to definite descriptions, they are also compatible with views that treat definite descriptions as basically scopeless. They thus provide no reason to see (...) definite descriptions as quantifiers. Even so, this paper shows that the examples do raise a surprising range of complex issues about how quantifier scope works, and where it occurs. Thus, a clear picture of how these examples work will help us to understand better where definite descriptions fit into the larger picture of quantifiers and related phenomena. (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)

We have recently started to understand that fundamental aspects of complex systems such as emergence, the measurement problem, inherent uncertainty, complex causality in connection with unpredictable determinism, time­irreversibility and non­locality all highlight the observer's participatory role in determining their workings. In addition, the principle of 'limited universality' in complex systems, which prompts us to search for the appropriate 'level of description in which unification and universality can be expected', looks like a version of Bohr's 'complementarity principle'. It is more or (...) less certain that the different levels of description possible of a complex whole ­­ actually partial objectifications ­­ are projected on to and even redefine its constituent parts. Thus it is interesting that these fundamental complexity issues don't just bear a formal resemblance to, but reveal a profound connection with, quantum mechanics. Indeed, they point to a common origin on a deeper level of description. (shrink)

While proper names in argument positions have received a lot of attention, this cannot be said about proper names in the naming construction, as in “Call me Al”. I argue that in a number of more or less familiar languages the syntax of naming constructions is such that proper names there have to be analyzed as predicates, whose content mentions the name itself (cf. “quotation theories”). If proper names can enter syntax as predicates, then in argument positions they should have (...) a complex structure, consisting of a determiner and its restriction, like common nouns (cf. “definite description theories of proper names”). Further consideration of the compositional semantics of proper names in the naming construction also shows that they have another argument slot, that of the naming convention. As a result, we will be able to account for the indexicality of proper names in argument positions and provide compositional semantics of complex and modified proper names (e.g., the famous detective Sherlock Holmes ). (shrink)

A categorical, higher dimensional algebra and generalized topos framework for Łukasiewicz–Moisil Algebraic–Logic models of non-linear dynamics in complex functional genomes and cell interactomes is proposed. Łukasiewicz–Moisil Algebraic–Logic models of neural, genetic and neoplastic cell networks, as well as signaling pathways in cells are formulated in terms of non-linear dynamic systems with n-state components that allow for the generalization of previous logical models of both genetic activities and neural networks. An algebraic formulation of variable ‘next-state functions’ is extended to a Łukasiewicz–Moisil (...) Topos with an n-valued Łukasiewicz–Moisil Algebraic Logic subobject classifier description that represents non-random and non-linear network activities as well as their transformations in developmental processes and carcinogenesis. The unification of the theories of organismic sets, molecular sets and Robert Rosen’s (M,R)-systems is also considered here in terms of natural transformations of organismal structures which generate higher dimensional algebras based on consistent axioms, thus avoiding well known logical paradoxes occurring with sets. Quantum bionetworks, such as quantum neural nets and quantum genetic networks, are also discussed and their underlying, non-commutative quantum logics are considered in the context of an emerging Quantum Relational Biology. (shrink)

We introduce SO-HORNr which is a revised version of SO-HORN and show that SO-HORNr captures equation image on ordered finite structures. We also introduce second-order extended Horn logic SO-EHORN and a superclass SO-EHORNr of it. We show that both of them capture equation image on ordered finite structures by proving that SO-EHORN and SO-EHORNr have the same expressive power when only consider ordered structures.