Human cognition is unique in the way in which it relies on combinatorial (or compositional) structures. Language provides ample evidence for the existence of combinatorial structures, but they can also be found in visual cognition. To understand the neural basis of human cognition, it is therefore essential to understand how combinatorial structures can be instantiated in neural terms. In his recent book on the foundations of language, Jackendoff described four fundamental problems for a neural instantiation of (...) class='Hi'>combinatorial structures: the massiveness of the binding problem, the problem of 2, the problem of variables, and the transformation of combinatorial structures from working memory to long-term memory. This paper aims to show that these problems can be solved by means of neural “blackboard” architectures. For this purpose, a neural blackboard architecture for sentence structure is presented. In this architecture, neural structures that encode for words are temporarily bound in a manner that preserves the structure of the sentence. It is shown that the architecture solves the four problems presented by Jackendoff. The ability of the architecture to instantiate sentence structures is illustrated with examples of sentence complexity observed in human language performance. Similarities exist between the architecture for sentence structure and blackboard architectures for combinatorial structures in visual cognition, derived from the structure of the visual cortex. These architectures are briefly discussed, together with an example of a combinatorial structure in which the blackboard architectures for language and vision are combined. In this way, the architecture for language is grounded in perception. Perspectives and potential developments of the architectures are discussed. Key Words: binding; blackboard architectures; combinatorial structure; compositionality; language; dynamic system; neurocognition; sentence complexity; sentence structure; working memory; variables; vision. (shrink)

In language, recombination of a discrete set of meaningless building blocks forms an unlimited set of possible utterances. How such combinatorial structure emerged in the evolution of human language is increasingly being studied. It has been shown that it can emerge when languages culturally evolve and adapt to human cognitive biases. How the emergence of combinatorial structure interacts with the existence of holistic iconic form-meaning mappings in a language is still unknown. The experiment presented in this (...) paper studies the role of iconicity and human cognitive learning biases in the emergence of combinatorial structure in artificial whistled languages. Participants learned and reproduced whistled words for novel objects with the use of a slide whistle. Their reproductions were used as input for the next participant, to create transmission chains and simulate cultural transmission. Two conditions were studied: one in which the persistence of iconic form-meaning mappings was possible and one in which this was experimentally made impossible. In both conditions, cultural transmission caused the whistled languages to become more learnable and more structured, but this process was slightly delayed in the first condition. Our findings help to gain insight into when and how words may lose their iconic origins when they become part of an organized linguistic system. (shrink)

Various issues concerning the neural blackboard architectures for combinatorial structures are discussed and clarified. They range from issues related to neural dynamics, the structure of the architectures for language and vision, and alternative architectures, to linguistic issues concerning the language architecture. Particular attention is given to the nature of true combinatorial structures and the way in which information can be retrieved from them in a productive and systematic manner.

Traditional combinatory logic uses combinators S and K to represent all Turing-computable functions on natural numbers, but there are Turing-computable functions on the combinators themselves that cannot be so represented, because they access internal structure in ways that S and K cannot. Much of this expressive power is captured by adding a factorisation combinator F. The resulting SF-calculus is structure complete, in that it supports all pattern-matching functions whose patterns are in normal form, including a function that decides (...) structural equality of arbitrary normal forms. A general characterisation of the structure complete, confluent combinatory calculi is given along with some examples. These are able to represent all their Turing-computable functions whose domain is limited to normal forms. The combinator F can be typed using an existential type to represent internal type information. (shrink)

Understanding whether the long and elaborate songs of male gibbons have syntax and hierarchical structures is an interesting question in the evolution of language, because gibbons are near humans in the phylogenetic tree and a hierarchically organized syntax is considered to be a basic component of human language. We conducted field research at Danum Valley Conservation Area in northern Borneo to test the hypothesis that gibbon songs have syntax and chunks. We followed one Mueller’s gibbon group for 1 week in (...) the dry and rainy seasons every year from 2001 to 2009, collecting vocal and behavioral data. Results show that songs emitted by the studied male gibbon were governed by combinatory rules. Some context-dependent songs had different combinatory rules, although they overlapped with the songs whose contexts were uncertain. The male Mueller’s songs had characteristics that suggest existence of chunk structure. These results provided an important perspective in the study of language origin. (shrink)

The regulation of glucose dehydrogenase (GLD) in Drosophila illustrates the combinatorial aspects of gene regulation in development. Furthermore, the findings serve to point up a general question about cukaryotic structural gene control: is regulation of expression always optimal?

Any theory of how language is internally organized and how it interacts with other mental capacities must address the fundamental question of how syntactic and lexico-semantic information interact at one central linguistic compositional level, the sentence level. With this general objective in mind, we examine ““lightverbs””, so called because the main thrust of the semantic relations of the predicate that they denote is found not in the predicate itself, but in the argument structure of the syntactic object that such (...) a predicate licenses. For instance, in the sentence.. (shrink)

Inside a combinatory algebra, there are ‘internal’ versions of the finite type structure over ω, which form models of various systems of finite type arithmetic. This paper compares internal representations of the intensional and extensional functionals. If these classes coincide, the algebra is called ft-extensional. Some criteria for ft-extensionality are given and a number of well-known ca's are shown to be ft-extensional, regardless of the particular choice of representation for ω. In particular, DA, Pω, Tω, Hω and certain D∞-models (...) all share the property of ft-extensionality. It is also shown that ft-extensionality is by no means an intrinsic property of ca's i.e., that there exists a very concrete class of ca's—the class of reflexive coherence spaces—no member of which has this property. This leads to a comparison of ft-extensionality with the well-studied notions of extensionality and weak extensionality. Ft-extensionality turns out to be completely independent. (shrink)

Combinatory logic started as a programme in the foundation of mathematics and in an historical context at a time when such endeavours attracted the most gifted among the mathematicians. This small volume arose under quite differ ent circumstances, namely within the context of reworking the mathematical foundations of computer science. I have been very lucky in finding gifted students who agreed to work with me and chose, for their Ph. D. theses, subjects that arose from my own attempts 1 to (...) create a coherent mathematical view of these foundations. The result of this collaborative work is presented here in the hope that it does justice to the individual contributor and that the reader has a chance of judging the work as a whole. E. Engeler ETH Zurich, April 1994 lCollected in Chapter III, An Algebraization of Algorithmics, in Algorithmic Properties of Structures, Selected Papers of Erwin Engeler, World Scientific PubJ. Co. , Singapore, 1993, pp. 183-257. I Historical and Philosophical Background Erwin Engeler In the fall of 1928 a young American turned up at the Mathematical Institute of Gottingen, a mecca of mathematicians at the time; he was a young man with a dream and his name was H. B. Curry. He felt that he had the tools in hand with which to solve the problem of foundations of mathematics mice and for all. His was an approach that came to be called "formalist" and embodied that later became known as Combinatory Logic. (shrink)

Logical geometry systematically studies Aristotelian diagrams, such as the classical square of oppositions and its extensions. These investigations rely heavily on the use of bitstrings, which are compact combinatorial representations of formulas that allow us to quickly determine their Aristotelian relations. However, because of their general nature, bitstrings can be applied to a wide variety of topics in philosophical logic beyond those of logical geometry. Hence, the main aim of this paper is to present a systematic technique for assigning (...) bitstrings to arbitrary finite fragments of formulas in arbitrary logical systems, and to study the logical and combinatorial properties of this technique. It is based on the partition of logical space that is induced by a given fragment, and sheds new light on a number of interesting issues, such as the logic-dependence of the Aristotelian relations and the subtle interplay between the Aristotelian and Boolean structure of logical fragments. Finally, the bitstring technique also allows us to systematically analyze fragments from contemporary logical systems, such as public announcement logic, which could not be done before. (shrink)

We study the fine structure of the core model for one Woodin cardinal, building of the work of Mitchell and Steel on inner models of the form . We generalize to some combinatorial principles that were shown by Jensen to hold in L. We show that satisfies the statement: “□κ holds whenever κ the least measurable cardinal λ of order λ++”. We introduce a hierarchy of combinatorial principles □κ, λ for 1 λ κ such that □κ□κ, 1 (...) □κ, λ □κ, κ□κ*. We prove that if holds in V. As an application, we show that ZFC + PFA Con. We also obtain one Woodin cardinal as a lower bound on the consistency strength of stationary reflection at κ+ for a singular, countably closed limit cardinal κ such that # exists; likewise for the failure of □κ* at such a κ. (shrink)

We employ the notions of "sequential function" and "interrogation" (dialogue) in order to define new partial combinatory algebra structures on sets of functions. These structures are analyzed using Longley's preorder-enriched category of partial combinatory algebras and decidable applicative structures. We also investigate total combinatory algebras of partial functions. One of the results is that every realizability topos is a geometric quotient of a realizability topos on a total combinatory algebra.

The aim of this paper is to show that topology has a bearing on<br><br>combinatorial theories of possibility. The approach developed in this article is “mapping account” considering combinatorial worlds as mappings from individuals to properties. Topological structures are used to define constraints on the mappings thereby characterizing the “really possible” combinations. The mapping approach avoids the well-known incompatibility problems. Moreover, it is compatible with atomistic as well as with non-atomistic ontologies.It helps to elucidate the positions of logical atomism (...) and monism with theaid of topological separation axioms. (shrink)

Given an admissible indexing φ of the countable atomless Boolean algebra B, an automorphism F of B is said to be recursively presented (relative to φ) if there exists a recursive function $p \in \operatorname{Sym}(\omega)$ such that F ⚬ φ = φ ⚬ p. Our key result on recursiveness: Both the subset of $\operatorname{Aut}(\mathscr{B})$ consisting of all those automorphisms which are recursively presented relative to some indexing, and its complement, the set of all "totally nonrecursive" automorphisms, are uncountable. This arises (...) as a consequence of the following combinatorial investigations: (1) A comparison of the cycle structures of f and f̄, where f is a permutation of some free basis of B and f̄ is the automorphism of B induced by f. (2) An explicit description of the permutations of ω whose conjugacy classes in $\operatorname{Sym}(\omega)$ are (a) uncountable, (b) countably infinite, and (c) finite. (shrink)

Deferential Monadic Panpsychism is a view that accepts that physical science is capable of discovering the basic structure of reality. However, it denies that reality is fully and exhaustively de- scribed purely in terms of physical science. Consciousness is missing from the physical description and cannot be reduced to it. DMP explores the idea that the physically fundamental features of the world possess some intrinsic mental aspect. It thereby faces a se- vere problem of understanding how more complex mental (...) states emerge from the mental features of the fundamental features. Here I explore the idea that a new form of aggregative emergence, which I call 'combinatorial infusion', could shed light on this problem and bolster the prospects for this form of panpsychism. (shrink)

The results of this paper extend some of the intimate relations that are known to obtain between combinatory logic and certain substructural logics to establish a general characterization theorem that applies to a very broad family of such logics. In particular, I demonstrate that, for every combinator X, if LX is the logic that results by adding the set of types assigned to X (in an appropriate type assignment system, TAS) as axioms to the basic positive relevant logic B∘T, then (...) LX is sound and complete with respect to the class of frames in the Routley-Meyer relational semantics for relevant and substructural logics that meet a first-order condition that corresponds in a very direct way to the structure of the combinator X itself. (shrink)

A crucial design feature of language useful for determining when grammatical language evolved in the human lineage is our ability to combine meaningless units to form a new unit with meaning (combinatoriality) and to further combine these meaningful units into a larger unit with a novel meaning (compositionality). There is overlap between neural bases that underlie hierarchical cognitive functions required for compositionality in both linguistic and nonlinguistic contexts (e.g., tool use). Therefore, evidence of compositional tool use in the archaeological record (...) should signify, at the very least, the cognitive capacity for grammatical language by that point in time. We devise a novel system to evaluate the level of hierarchical nesting of tool components in single tool use activities. In the application of this system, we demonstrate that nonhuman primates, and by extension, the last common ancestor shared by Pan and Homo, are capable of basic combinatoriality; however, their technology does not approach the compositionality observable in modern human tool use. The prehistoric archaeological record supports a continuous evolution of combinatorial tool use into compositional tool use, with evidence for human-like levels of by 0.93 million years ago (Ma), or possibly as early as 1.7 Ma. While compositional language could have lagged behind compositional tool use, if language and technology coevolved according to the Technological Origin for Language hypothesis, which proposes a feedback system between the two, then evidence for hierarchical tool use structures implies a similar level of complexity in linguistic structures. (shrink)

Assuming 0 ♯ does not exist, we present a combinatorial approach to Jensen's method of coding by a real. The forcing uses combinatorial consequences of fine structure (including the Covering Lemma, in various guises), but makes no direct appeal to fine structure itself.

Partial combinatory algebras (pcas) are algebraic structures that serve as generalized models of computation. In this article, we study embeddings of pcas. In particular, we systematize the embeddings between relativizations of Kleene’s models, of van Oosten’s sequential computation model, and of Scott’s graph model, showing that an embedding between two relativized models exists if and only if there exists a particular reduction between the oracles. We obtain a similar result for the lambda calculus, showing in particular that it cannot be (...) embedded in Kleene’s first model. (shrink)

The dissertation deals with problems in "logic", more precisely, it deals with particular formal systems aiming at capturing patterns of valid reasoning. Sequent calculi were proposed to characterize logical connectives via introduction rules. These systems customarily also have structural rules which allow one to rearrange the set of premises and conclusions. In the "structurally free logic" of Dunn and Meyer the structural rules are replaced by combinatory rules which allow the same reshuffling of formulae, and additionally introduce an explicit marker (...) for the application of the rule---the combinator. The dissertation gives syntactic extensions of such systems introducing conjunction and disjunction . Cut elimination is proved for these systems. ;Syntactic systems as a rule are accompanied by a semantics which interprets them. The extended systems are supplied with semantics using algebraic methods. First, the Lindenbaum algebras are formed, and then these algebras are represented in an algebra of sets. This gives a so called Kripke-style semantics for the systems. The representation for the distributive extension utilizes well-known techniques; it uses sets of prime filters and set theoretical operations on them to deal with conjunction and disjunction, plus a ternary accessibility relation to accommodate the intensional operators as fusion and implication. The representation theorem is proven generally, i.e., for arbitrary sets of combinators using the "squeeze lemma" of Routley and Meyer. ;The non-distributive calculi require a different representation since union and intersection are distributive. Two previous representations for lattices are overviewed, and a modification of the Hartonas-Dunn representation is successfully augmented with the intensional operations. Instead of sets of filters, sets of pairs of minimally inconsistent filters and ideals are used and the representation theorem is proven. The representation results provide soundness and completeness for the systems. The dissertation also investigates properties of dual combinators , proving a series of lemmas about dual combinatory systems not being Church-Rosser and being inconsistent. Combinatorially definable classes of lambda-terms are considered as well. (shrink)

Within the field of causal inference, it is desirable to learn the structure of causal relationships holding between a system of variables from the correlations that these variables exhibit; a sub-problem of which is to certify whether or not a given causal hypothesis is compatible with the observed correlations. A particularly challenging setting for assessing causal compatibility is in the presence of partial information; i.e. when some of the variables are hidden/latent. This paper introduces the possible worlds framework as (...) a method for deciding causal compatibility in this difficult setting. We define a graphical object called a possible worlds diagram, which compactly depicts the set of all possible observations. From this construction, we demonstrate explicitly, using several examples, how to prove causal incompatibility. In fact, we use these constructions to prove causal incompatibility where no other techniques have been able to. Moreover, we prove that the possible worlds framework can be adapted to provide a complete solution to the possibilistic causal compatibility problem. Even more, we also discuss how to exploit graphical symmetries and cross-world consistency constraints in order to implement a hierarchy of necessary compatibility tests that we prove converges to sufficiency. (shrink)

In which respects do modeling and experimenting resemble or differ from each other? We explore this question through studying in detail the combinatorial strategy in synthetic biology whereby scientists triangulate experimentation on model organisms, mathematical modeling, and synthetic modeling. We argue that this combinatorial strategy is due to the characteristic constraints of the three epistemic activities. Moreover, our case study shows that in some cases materiality clearly matters, in fact it provides the very rationale of synthetic modeling. We (...) will show how the materialities of the different kinds of models – biological components versus mathematical symbols – in combination with their different structures – the complexity of biological organisms versus the isolated network structure and its mathematical dynamics - define the spectrum of epistemic possibilities in synthetic biology. Furthermore, our case shows that from the perspective of scientific practice the question of whether or not simulations are like or unlike experiments is often beside the point, since they are used to accomplish different kinds of things. (shrink)

The aim of this paper is to offer two novel solutions to two perennial problems of categorial ontology, namely, the problem of the categorial structure: how are the categories related to one another? And the problem of categorial completeness: how is the completeness of a proposed list of categories justified? First, I argue that a system of categories should have a structure such that there is a most basic category that is a bearer of all other categories and (...) that has what I shall call “combinatorial conditions”. To do so, I compare this approach to categorial structure with the approaches given by substantialist, mereological, factualist, and geo ontologies. Second, I argue that the problem of categorial completeness is only a problem for certain ontologies. In this connection, I explore views on categorial completeness proposed by substantialists and geo-ontologists. Lastly, I conclude that factualism does a better job of accounting for categorial structure and categorial completeness than other categorial ontologies. (shrink)

Symmetic combinatory logic with the symmetric analogue of a combinatorially complete base (in the form of symmetric λ-calculus) is known to lack the Church-Rosser property. We prove a much stronger theorem that no symmetric combinatory logic that contains at least two proper symmetric combinators has the Church-Rosser property. Although the statement of the result looks similar to an earlier one concerning dual combinatory logic, the proof is different because symmetric combinators may form redexes in both left and right associated terms. (...) Perhaps surprisingly, we are also able to show that certain symmetric combinatory logics that include just one particular constant are not confluent. This result (beyond other differences) clearly sets apart symmetric combinatory logic from dual combinatory logic, since all dual combinatory systems with a single combinator or a single dual combinator are Church-Rosser. Lastly, we prove that a symmetric combinatory logic that contains the fixed point and the one-place identity combinator has the Church-Rosser property. (shrink)

Symmetic combinatory logic with the symmetric analogue of a combinatorially complete base (in the form of symmetric λ-calculus) is known to lack the Church-Rosser property. We prove a muchstrongertheorem that no symmetric combinatory logic that containsat least two proper symmetric combinatoryhas the Church-Rosser property. Although the statement of the result looks similar to an earlier one concerning dual combinatory logic,the proof is differentbecause symmetric combinators may form redexes in both left and right associated terms. Perhaps surprisingly, we are also able (...) to show that certain symmetric combinatory logics that include justone particular constantare not confluent. This result (beyond other differences) clearly sets apart symmetric combinatory logic from dual combinatory logic, since all dual combinatory systems with a single combinator or a single dual combinator are Church-Rosser. Lastly, we prove that a symmetric combinatory logic that contains the fixed point and the one-place identity combinator has the Church-Rosser property. (shrink)

Topics covered in Discrete Mathematics have become essential tools in many areas of studies in recent years. This is primarily due to the revolution in technology, communications, and cyber security. The book treats major themes in a typical introductory modern Discrete Mathematics course: Propositional and predicate logic, proof techniques, set theory (including Boolean algebra, functions and relations), introduction to number theory, combinatorics and graph theory. An accessible, precise, and comprehensive approach is adopted in the treatment of each topic. The ability (...) of abstract thinking and the art of writing valid arguments are emphasized through detailed proof of (almost) every result. Developing the ability to think abstractly and roguishly is key in any areas of science, information technology and engineering. Every result presented in the book is followed by examples and applications to consolidate its comprehension. The hope is that the reader ends up developing both the abstract reasoning as well as acquiring practical skills. All efforts are made to write the book at a level accessible to first-year students and to present each topic in a way that facilitates self-directed learning. Each chapter starts with basic concepts of the subject at hand and progresses gradually to cover more ground on the subject. Chapters are divided into sections and subsections to facilitate readings. Each section ends with its own carefully chosen set of practice exercises to reenforce comprehension and to challenge and stimulate readers. As an introduction to Discrete Mathematics, the book is written with the smallest set of prerequisites possible. Familiarity with basic mathematical concepts (usually acquired in high school) is sufficient for most chapters. However, some mathematical maturity comes in handy to grasp some harder concepts presented in the book. (shrink)

Research in anthropology has shown that kin terminologies have a complex combinatorial structure and vary systematically across cultures. This article argues that universals and variation in kin terminology result from the interaction of (1) an innate conceptual structure of kinship, homologous with conceptual structure in other domains, and (2) principles of optimal, “grammatical” communication active in language in general. Kin terms from two languages, English and Seneca, show how terminologies that look very different on the surface (...) may result from variation in the rankings of a universal set of constraints. Constraints on kin terms form a system: some are concerned with absolute features of kin (sex), others with the position (distance and direction) of kin in “kinship space,” others with groups and group boundaries (matrilines, patrilines, generations, etc.). Also, kin terms sometimes extend indefinitely via recursion, and recursion in kin terminology has parallels with recursion in other areas of language. Thus the study of kinship sheds light on two areas of cognition, and their phylogeny. The conceptual structure of kinship seems to borrow its organization from the conceptual structure of space, while being specialized for representing genealogy. And the grammar of kinship looks like the product of an evolved grammar faculty, opportunistically active across traditional domains of semantics, syntax, and phonology. Grammar is best understood as an offshoot of a uniquely human capacity for playing coordination games. (shrink)

Dual combinators emerge from the aim of assigning formulas containing ← as types to combinators. This paper investigates formally some of the properties of combinatory systems that include both combinators and dual combinators. Although the addition of dual combinators to a combinatory system does not affect the unique decomposition of terms, it turns out that some terms might be redexes in two ways (with a combinator as its head, and with a dual combinator as its head). We prove a general (...) theorem stating that no dual combinatory system possesses the Church-Rosser property. Although the lack of confluence might be problematic in some cases, it is not a problem per se. In particular, we show that no damage is inflicted upon the structurally free logics, the system in which dual combinators first appeared. (shrink)

To model behavioral and neural correlates of language comprehension in naturalistic environments, researchers have turned to broad‐coverage tools from natural‐language processing and machine learning. Where syntactic structure is explicitly modeled, prior work has relied predominantly on context‐free grammars (CFGs), yet such formalisms are not sufficiently expressive for human languages. Combinatory categorial grammars (CCGs) are sufficiently expressive directly compositional models of grammar with flexible constituency that affords incremental interpretation. In this work, we evaluate whether a more expressive CCG provides a (...) better model than a CFG for human neural signals collected with functional magnetic resonance imaging (fMRI) while participants listen to an audiobook story. We further test between variants of CCG that differ in how they handle optional adjuncts. These evaluations are carried out against a baseline that includes estimates of next‐word predictability from a transformer neural network language model. Such a comparison reveals unique contributions of CCG structure‐building predominantly in the left posterior temporal lobe: CCG‐derived measures offer a superior fit to neural signals compared to those derived from a CFG. These effects are spatially distinct from bilateral superior temporal effects that are unique to predictability. Neural effects for structure‐building are thus separable from predictability during naturalistic listening, and those effects are best characterized by a grammar whose expressive power is motivated on independent linguistic grounds. (shrink)

The International Workshop on Combinatorial Algorithms was established in 1989 as the Australasian Workshop on Combinatorial Algorithms. As a consequence of the workshop's success in attracting mathematicians and computer scientists from around the world, it was decided at the 2006 meeting to go global, to change the workshop's name, and to hold it in appropriate venues around the world. The workshop supports basic research on the interface between mathematics and computing, specifically * Algorithms & Data Structures * Complexity (...) Theory * Algorithms on Graphs & Strings * Combinatorial Optimization * Cryptography & Information Security * Computational Biology * Communications Networks and many other related areas. This is Volume 1 in the series of IWOCA proceedings. See http: //www.iwoca.org/. (shrink)

Human language is a salient example of a neurocognitive system that is specialized to process complex dependencies between sensory events distributed in time, yet how this system evolved and specialized remains unclear. Artificial Grammar Learning (AGL) studies have generated a wealth of insights into how human adults and infants process different types of sequencing dependencies of varying complexity. The AGL paradigm has also been adopted to examine the sequence processing abilities of nonhuman animals. We critically evaluate this growing literature in (...) species ranging from mammals (primates and rats) to birds (pigeons, songbirds, and parrots) considering also cross‐species comparisons. The findings are contrasted with seminal studies in human infants that motivated the work in nonhuman animals. This synopsis identifies advances in knowledge and where uncertainty remains regarding the various strategies that nonhuman animals can adopt for processing sequencing dependencies. The paucity of evidence in the few species studied to date and the need for follow‐up experiments indicate that we do not yet understand the limits of animal sequence processing capacities and thereby the evolutionary pattern. This vibrant, yet still budding, field of research carries substantial promise for advancing knowledge on animal abilities, cognitive substrates, and language evolution. (shrink)

In this dissertation we explore projective Fraïssé theory and its applications, as well as limitations, to the study of compact metrizable spaces. The goal of projective Fraïssé theory is to approximate spaces via classes of finite structures and glean topological or dynamical properties of a space by relating them to combinatorial features of the associated class of structures. Using the framework of compact metrixable structures, we establish general results which expand and help contextualize previous works in the field. Many (...) proofs in the domain of projective Fraïssé theory are carried out in a context dependent fashion and have thus far eluded clean generalizations. A reason is to be found in the lack of a clear understanding of which spaces are amenable to be studied via projective Fraïssé limits. We give both positive and negative results in this direction. We isolate a combinatorial condition which entails a correspondence between finite structures and regular quasi-partitions of compact metrizable spaces. This correspondence greatly aids the combinatorial-toplogical translation. We apply this machinery to study a class of one-dimensional compact metrizable spaces, which we call smooth fences. To this end, we isolate a class of finite structures—finite partial orders whose Hasse diagram is a forest—whose projective Fraïssé limit approximates a distinctive smooth fence with remarkable properties. We call it the Fraïssé fence and characterize it topologically by carefully exploiting the bridge between the combinatorial and topological worlds. We explore homogeneity and universality features of the Fraïssé fence and the properties of its spaces and endpoints, and provide some results on the dynamics of its group of homeomorphisms. The dissertation is partially based on [1, 2]. (shrink)

Ramsey algebras are an attempt to investigate Ramsey spaces generated by algebras in a purely combinatorial fashion. Previous studies have focused on the basic properties of Ramsey algebras and a few specific examples. In this article, we study the properties of Ramsey algebras from a structural point of view. For instance, we will see that isomorphic algebras have the same Ramsey algebraic properties, but elementarily equivalent algebras need not be so, as expected. We also answer an open question about (...) Cartesian products of Ramsey algebras. (shrink)

RNAs have emerged as a major target for diagnostics and therapeutics approaches. Regulatory nonprotein‐coding RNAs (ncRNAs) in particular display remarkable versatility. They can fold into complex structures and interact with proteins, DNA, and other RNAs, thus modulating activity, localization, or interactome of multi‐protein complexes. Thus, ncRNAs confer regulatory plasticity and represent a new layer of regulatory control. Interestingly, long noncoding RNAs (lncRNAs) tend to acquire complex secondary and tertiary structures and their function—in many cases—is dependent on structural conservation rather than (...) primary sequence conservation.Whereas for many proteins, structure and its associated function are closely connected, for lncRNAs, the structural domains that determine functionality and its interactome are still not well understood. Numerous approaches for analyzing the structural configuration of lncRNAs have been developed recently. Here, will provide an overview of major experimental approaches used in the field, and discuss the potential benefit of using combinatorial strategies to analyze lncRNA modes of action based on structural information. (shrink)

The present investigation challenges the traditional distinction between cohesion and coherence; i.e., the distinction between the syntactical rules governing the composition of lexical units within the scope of the clause and the semantic-pragmatic rules guiding the composition of text units beyond the scope of the clause. To this end it exposes two major principles of semantic combination that are active through all levels of linguistic composition: viz. frame-schematic structure and narrative structure. These principles are considered as being components (...) of a semantic combinatorial system to be determined in terms of dependency relations. (shrink)

The present investigation challenges the traditional distinction between cohesion and coherence; i.e., the distinction between the syntactical rules governing the composition of lexical units within the scope of the clause and the semantic-pragmatic rules guiding the composition of text units beyond the scope of the clause. To this end it exposes two major principles of semantic combination that are active through all levels of linguistic composition: viz. frame-schematic structure and narrative structure. These principles are considered as being components (...) of a semantic combinatorial system to be determined in terms of dependency relations. (shrink)

A 'Kripke-style' semantics is given for combinatory logic using frames with a ternary accessibility relation, much as in the Tourley-Meyer semantics for relevance logic. We prove by algebraic means a completeness theorem for combinatory logic, by proving a representation theorem for 'combinatory posets.' A philosophical interpretation is given of the models, showing that an element of a combinatory poset can be understood simultaneously as a set of states and as a set of actions on states. This double interpretation allows for (...) one such element to be applied to another . Application turns out to be modeled the same way as 'fusion' in relevance logic.We also introduce 'dual combinators' that apply from the right. We then explore relationships to some well-known substructural logics, showing that each can be embedded into the structurally free. non-associative Lambek calculus, with the embedding taking a theorem ω to a statement of the form Γ ⊨ ω, where Γ is some fusion of the combinators needed to justify the structural assumptions of the given substructural logic. This builds on earlier ideas from Belnap and Meyer about a Gentzen system wherein structural rules are replaced with rules for introducing combinators. We develop such a system and prove a cut theorem. (shrink)

Several papers (e.g. [7, 23, 42]) have recently sought to give general frameworks for online structures and algorithms ([4]), and seeking to connect, if only by analogy, online and computable structure theory. These initiatives build on earlier work on online colouring and other combinatorial algorithms by Bean [10], Kierstead, Trotter et al. [48, 54, 57] and others, as we discuss below. In this paper we will look at such frameworks and illustrate them with examples from the first author’s (...) MSc Thesis ([58]). In this thesis, Askes looks at online, adversarial online and strongly online algorithms and structures. Additionally, we prove some new theorems about online algorithms on graphs of bounded pathwidth as well as some new results on punctually 1-decidable structures. (shrink)

We define the notion of a combinatorics of a first order structure, and a relation of covering between first order structures and propositional proof systems. Namely, a first order structure M combinatorially satisfies an L-sentence Φ iff Φ holds in all L-structures definable in M. The combinatorics Comb(M) of M is the set of all sentences combinatorially satisfied in M. Structure M covers a propositional proof system P iff M combinatorially satisfies all Φ for which the associated (...) sequence of propositional formulas 〈Φ〉 n , encoding that Φ holds in L-structures of size n, have polynomial size P-proofs. That is, Comb(M) contains all Φ feasibly verifiable in P. Finding M that covers P but does not combinatorially satisfy Φ thus gives a super polynomial lower bound for the size of P-proofs of 〈Φ〉 n . We show that any proof system admits a class of structures covering it; these structures are expansions of models of bounded arithmetic. We also give, using structures covering proof systems R * (log) and PC, new lower bounds for these systems that are not apparently amenable to other known methods. We define new type of propositional proof systems based on a combinatorics of (a class of) structures. (shrink)

This commentary focuses on the nature of combinatorial properties for speech and the locus equation. The presence of some overlap in locus equation space suggests that this higher order property may not be strictly invariant and may require other cues or properties for the perception of place of articulation. Moreover, combinatorial analysis in two-dimensional space and the resultant linearity appear to have a “special” status in the development of this theoretical framework. However, place of articulation is only one (...) of many phonetic dimensions in language. It is suggested that a multidimensional space including patterns derived in the frequency, amplitude, and time domains will be needed to characterize the phonetic categories of speech, and that although the derived properties ultimately may not meet the conditions of linearity, they will reflect a higher order acoustic invariance. (shrink)

In this paper we introduce a collection of isols having some interesting properties. Imagine a collection W of regressive isols with the following features: u, v ϵ W implies that u ⩽ v or v ⩽ u, u ⩽ v and v ϵ W imply u ϵ W, W contains ℕ = {0,1,2,…} and some infinite isols, and u eϵ W, u infinite, and u + v regressive imply u + v ϵ W. That such a collection W exists is (...) proved in our paper. It has many nice features. It also satisfies u, v ϵ W, u ⩽ v and u infinite imply v ⩽ g for some recursive combinatorial function g, and each u ϵ W is hereditarily odd-even and is hereditarily recursively strongly torre. The collection W that we obtain may be characterized in terms of a semiring of isols D introduced by J. C. E. Dekker in [5]. We will show that W = D, where c is an infinite regressive isol that is called completely torre. (shrink)

The complex organization of syntax in hierarchical structures is one of the core design features of human language. Duality of patterning refers, for instance, to the organization of the meaningful elements in a language at two distinct levels: a combinatorial level, where meaningless forms are combined into meaningful forms; and a compositional level, where meaningful forms are composed into larger lexical units. The question remains wide open regarding how such structures could have emerged. The aim of this paper is (...) to address these two aspects in a self-consistent way. First, we introduce suitable measures to quantify the level of combinatoriality and compositionality in a language, and we present a framework to estimate these observables in human natural languages. Second, we show that a recently introduced multi-agent modeling scheme, namely the Blending Game, provides a mathematical framework to address the problem of how a population of individuals can bootstrap combinatoriality and compositionality. Theoretical predictions based on this model turn out to be in good agreement with empirical data. It is remarkable that the two sides of duality of patterning emerge simultaneously as a consequence of a pure cultural dynamics in a simulated environment that contains meaningful relations, provided a simple constraint on message transmission fidelity is also considered. (shrink)

Central to Elements is an assay of the attributional union properties and relations have with their subjects, a topic historically left metaphorical. The work critiques eight Aristotelian assumptions concerning attribute dependence and ‘inherence’, per se subjects, attributes as agent-organizers, and unity-by-a-shared-one. Groups of these assumptions are seen to yield contradiction, vicious regress, or other problems. This analysis, joined with insights from an assay of ubiquitous structure, motivate ten theses explicating attribution and its primary ontic status. The theses detail: attributes (...) proper as individuated instances, structure as instance-generated facts and their two forms of composition, the conditioning role and universal nature of instances’ component intensions, the primacy of attribute instances for generating all forms of composition and complex entities, and identity and indiscernibility criteria for the latter. Principal is the insight that attribution is intension-determined combinatorial agency. It is its systematizing implications that provide solutions to classic problems, e.g., Composition, Individuation, and Universals, and in net generate a comprehensive one-category structuralist ontology. (shrink)