Causal set theory and the theory of linear structures (which has recently been developed by Tim Maudlin as an alternative to standard topology) share some of their main motivations. In view of that, I raise and answer the question how these two theories are related to each other and to standard topology. I show that causal set theory can be embedded into Maudlin’s more general framework and I characterise what Maudlin’s topological concepts boil down to when applied to (...) discrete linear structures that correspond to causal sets. Moreover, I show that all topological aspects of causal sets that can be described in Maudlin’s theory can also be described in the framework of standard topology. Finally, I discuss why these results are relevant for evaluating Maudlin’s theory. The value of this theory depends crucially on whether it is true that (a) its conceptual framework is as expressive as that of standard topology when it comes to describing well-known continuous as well as discrete models of spacetime and (b) it is even more expressive or fruitful when it comes to analysing topological aspects of discrete structures that are intended as models of spacetime. On the one hand, my theorems support (a): the theory is rich enough to incorporate causal set theory and its definitions of topological notions yield a plausible outcome in the case of causal sets. On the other hand, the results undermine (b): standard topology, too, has the conceptual resources to capture those topological aspects of causal sets that are analysable within Maudlin’s framework. This fact poses a challenge for the proponents of Maudlin’s theory to prove it fruitful. (shrink)

Causal set theory and the theory of linear structures share some of their main motivations. In view of that, I raise and answer the question how these two theories are related to each other and to standard topology. I show that causal set theory can be embedded into Maudlin’s more general framework and I characterise what Maudlin’s topological concepts boil down to when applied to discrete linear structures that correspond to causal sets. Moreover, I show that (...) all topological aspects of causal sets that can be described in Maudlin’s theory can also be described in the framework of standard topology. Finally, I discuss why these results are relevant for evaluating Maudlin’s theory. The value of this theory depends crucially on whether it is true that its conceptual framework is as expressive as that of standard topology when it comes to describing well-known continuous as well as discrete models of spacetime and it is even more expressive or fruitful when it comes to analysing topological aspects of discrete structures that are intended as models of spacetime. On the one hand, my theorems support : the theory is rich enough to incorporate causal set theory and its definitions of topological notions yield a plausible outcome in the case of causal sets. On the other hand, the results undermine : standard topology, too, has the conceptual resources to capture those topological aspects of causal sets that are analysable within Maudlin’s framework. This fact poses a challenge for the proponents of Maudlin’s theory to prove it fruitful. (shrink)

Tim Maudlin sets out a completely new method for describing the geometrical structure of spaces, and thus a better mathematical tool for describing and understanding space-time. He presents a historical review of the development of geometry and topology, and then his original Theory of Linear Structures.

Recursive linear structural equation models can be represented by directed acyclic graphs. When represented in this way, they satisfy the Markov Condition. Hence it is possible to use the graphical d-separation to determine what conditional independence relations are entailed by a given linear structural equation model. I prove in this paper that it is also possible to use the graphical d-separation applied to a cyclic graph to determine what conditional independence relations are entailed to hold by a given (...) non-recursive linear structural equation model. I also give a causal intepretation to the linear coefficients in a non- recursive structural equation models, and explore the relationships between cyclic graphs and undirected graphs, directed acyclic graphs with latent variables, and chain independence graphs. (shrink)

O-minimal structures have long been thought to occupy the base of a hierarchy of ordered structures, in analogy with the role that strongly minimal structures play with respect to stable theories. This is the first in an anticipated series of papers whose aim is the development of model theory for ordered structures of rank greater than one. A class of ordered structures to which a notion of finite rank can be assigned, the decomposable structures, (...) is introduced here. These include all ordered structures definable in o-minimal structures. The principal result in this paper, Theorem 5.1, asserts roughly that a decomposable structure [Formula: see text] can be partitioned into finitely many definable subsets such that on each set the restriction of < is a "twisted lexicographic" order. As a consequence, for all n and linear orders ≺ definable on a subset X ⊆ Mn in an o-minimal structure [Formula: see text], there is a definable partition of X such that the restriction of ≺ to each set in the partition is "lexicographic". (shrink)

I study definability and types in the linear fragment of continuous logic. Linear variants of several definability theorems such as Beth, Svenonus and Herbrand are proved. At the end, a partial study of the theories of probability algebras, probability algebras with an aperiodic automorphism and AL-spaces is given.

This paper proposes an architecture for the mapping between syntax and phonology — in particular, that aspect of phonology that determines ordering. In Fox and Pesetsky (in prep.), we will argue that this architecture, when combined with a general theory of syntactic domains ("phases"), provides a new understanding of a variety of phenomena that have received diverse accounts in the literature. This shorter paper focuses on two processes, both drawn from Scandinavian: the familiar process of Object Shift and the less (...) well-known process of Quantifier Movement. We will argue that constraints on these operations can be seen as instances of the same property of grammar that explains the fact that movement is local and successive cyclic. We begin by sketching a model in which locality and successive cyclicity are consequences of the architecture that we propose, rather than specific facts about movement itself. We next present our proposal in somewhat greater detail, and show how it can account for a wide range of apparent limitations on movement — in particular, superficially contradictory restrictions on Object Shift and Quantifier Movement. The restrictions on Object Shift include those grouped under the rubric of Holmberg's Generalization, which Quantifier Movement does not seem to obey. We will argue that Quantifier Movement instead obeys a near mirror-image of Holmberg's Generalization (an "Inverse Holmberg Effect"), but that both Holmberg's Generalization and its mirror image are expected if our proposed architecture is correct. (shrink)

Shane Harwood and Richard Scheines. Learning Linear Causal Structure Equation Models with Genetic Algorithms.

This paper proposes an architecture for the mapping between syntax and phonology — in particular, that aspect of phonology that determines ordering. In Fox and Pesetsky (in prep.), we will argue that this architecture, when combined with a general theory of syntactic domains ("phases"), provides a new understanding of a variety of phenomena that have received diverse accounts in the literature. This shorter paper focuses on two processes, both drawn from Scandinavian: the familiar process of Object Shift and the less (...) well-known process of Quantifier Movement. We will argue that constraints on these operations can be seen as instances of the same property of grammar that explains the fact that movement is local and successive cyclic. We begin by sketching a model in which locality and successive cyclicity are consequences of the architecture that we propose, rather than specific facts about movement itself. We next present our proposal in somewhat greater detail, and show how it can account for a wide range of apparent limitations on movement — in particular, superficially contradictory restrictions on Object Shift and Quantifier Movement. The restrictions on Object Shift include those grouped under the rubric of Holmberg's Generalization, which Quantifier Movement does not seem to obey. We will argue that Quantifier Movement instead obeys a near mirror-image of Holmberg's Generalization (an "Inverse Holmberg Effect"), but that both Holmberg's Generalization and its mirror image are expected if our proposed architecture is correct. (shrink)

We describe anytime search procedures that (1) find disjoint subsets of recorded variables for which the members of each subset are d-separated by a single common unrecorded cause, if such exists; (2) return information about the causal relations among the latent factors so identified. We prove the procedure is point-wise consistent assuming (a) the causal relations can be represented by a directed acyclic graph (DAG) satisfying the Markov Assumption and the Faithfulness Assumption; (b) unrecorded variables are not caused by recorded (...) variables; and (c) dependencies are linear. We compare the procedure with standard approaches over a variety of simulated structures and sample sizes, and illustrate its practical value with brief studies of social science data sets. Finally, we consider generalizations for non-linear systems. Keywords: latent variable models, causality, graphical models.. (shrink)

Let $\scr{M}=\langle M,+,<,0,S\rangle $ be a linear o-minimal expansion of an ordered group, and $G=\langle G,\oplus ,e_{G}\rangle $ an n-dimensional group definable in $\scr{M}$ . We show that if G is definably connected with respect to the t-topology, then it is definably isomorphic to a definable quotient group U/L, for some convex ${\ssf V}\text{-definable}$ subgroup U of $\langle M^{n},+\rangle $ and a lattice L of rank equal to the dimension of the 'compact part' of G.

Pseudo-BCK-algebras are a non-commutative generalization of well-known BCK-algebras. The paper describes a situation when a linearly ordered pseudo-BCK-algebra is an ordinal sum of linearly ordered cone algebras. In addition, we present two identities giving such a possibility of the decomposition and axiomatize the residuation subreducts of representable pseudo-hoops and pseudo-BL-algebras.

Substructural logics are obtained from the sequent calculi for classical or intuitionistic logic by suitably restricting or deleting some or all of the structural rules (Restall, 2000; Ono, 1998). Recently, this field of research has come to encompass a number of logics - e.g. many fuzzy or paraconsistent logics - which had been originally introduced out of different, possibly semantical, motivations. A finer proof-theoretical analysis of such logics, in fact, revealed that it was possible to subsume them under the previous (...) definition (see e.g. Aguzzoli and Ciabattoni, 2000).Although proof systems for substructural logics are currently being investigated with remarkable success, their algebraic models do not seem equally satisfactory. In fact:(i) such structures are often very weak, i.e. they do not possess many interesting algebraic properties;(ii) as a consequence, their theories of ideals, congruences, and representation are as a rule scarcely developed, or even lacking.In this paper, we address these difficulties. (shrink)

A review of the literature indicates that linear models are frequently used in situations in which decisions are made on the basis of multiple codable inputs. These models are sometimes used normatively to aid the decision maker, as a contrast with the decision maker in the clinical vs statistical controversy, to represent the decision maker "paramorphically" and to "bootstrap" the decision maker by replacing him with his representation. Examination of the contexts in which linear models have been successfully (...) employed indicates that the contexts have the following structural characteristics in common: each input variable has a conditionally monotone relationship with the output; there is error of measurement; and deviations from optimal weighting do not make much practical difference. These characteristics ensure the success of linear models, which are so appropriate in such contexts that random linear models may perform quite well. 4 examples involving the prediction of such codable output variables as GPA and psychiatric diagnosis are analyzed in detail. In all 4 examples, random linear models yield predictions that are superior to those of human judges. (shrink)

We prove the Compact Domination Conjecture for groups definable in linear o-minimal structures. Namely, we show that every definably compact group G definable in a saturated linear o-minimal expansion of an ordered group is compactly dominated by (G/G 00, m, π), where m is the Haar measure on G/G 00 and π : G → G/G 00 is the canonical group homomorphism.

Linear structural equation models with latent (unmeasured) variables are used widely in sociology, psychometrics, and political science. When such models have a unidimensional..

This paper deals with the question of whether uncertainty regarding model structure, especially in climate modeling, exhibits a kind of “chaos.” Do small changes in model structure, in other words, lead to large variations in ensemble predictions? More specifically, does model error destroy forecast skill faster than the ordinary or “classical” chaos inherent in the real-world attractor? In some cases, the answer to this question seems to be “yes.” But how common is this state of affairs? Are there precise mathematical (...) results that can help us answer this question? And is dependence on model structure “sensitive” in that arbitrarily small errors can destroy forecast skill? We examine some efforts in the literature to answer this last question in the affirmative and find them to be unconvincing. (shrink)

In an unpublished note Reddy introduced an extended intuitionistic linear calculus, called LLMS (for Linear Logic Model of State), to model state manipulation via the notions of sequential composition and ‘regenerative values’. His calculus introduces the connective ‘before’ ▹ and an associated modality †, for the storage of objects sequentially reusable. Earlier and independently de Paiva introduced a (collection of) dialectica categorical models for (classical and intuitionistic) Linear Logic, the categories Dial2Set. These categories contain, apart from the (...) structure needed to model linear logic, an extra tensor product functor and an extra comonad structure corresponding to a modality related to the extra tensor product. It is surprising that these works arising from completely different motivations can be related in a meaningful way. In this article, following joint work with Corrêa and Haeusler, we first adapt Reddy's system LLMS providing a commutative version of the connective ‘before’ and its associated modality and then construct a dialectica category on Sets , which we show is a sound model for the modified version of Reddy's the system LLMSc. Moreover, following the work of Tucker, we provide another variant of the Dialectica categories with a non-commutative tensor and its associated modality, which models soundlyLLMS itself. We conclude with some speculation on future applications. (shrink)

We develop an extension of the familiar linear mixed logit model to allow for the direct estimation of parametric non-linear functions defined over structural parameters. Classic applications include the estimation of coefficients of utility functions to characterize risk attitudes and discounting functions to characterize impatience. There are several unexpected benefits of this extension, apart from the ability to directly estimate structural parameters of theoretical interest.

While specifications and verifications of concurrent systems employ Linear Temporal Logic , it is increasingly likely that logical consequence in image will be used in the description of computations and parallel reasoning. Our paper considers logical consequence in the standard image with temporal operations image and image . The prime result is an algorithm recognizing consecutions admissible in image, so we prove that image is decidable w.r.t. admissible inference rules. As a consequence we obtain algorithms verifying the validity of (...) consecutions in image and solving the satisfiability problem. We start by a simple reduction of logical consecutions of image to equivalent ones in the reduced normal form . Then we apply a semantic technique based on image-Kripke structures with formula definable subsets. This yields necessary and sufficient conditions for a consecution to be not admissible in image. These conditions lead to an algorithm which recognizes consecutions admissible in image by verifying the validity of consecutions in special finite Kripke structures of size square polynomial in reduced normal forms of the consecutions. As a consequence, this also solves the satisfiability problem for image. (shrink)

LetEbe a computably enumerable equivalence relation on the setωof natural numbers. We say that the quotient set$\omega /E$realizesa linearly ordered set${\cal L}$if there exists a c.e. relation ⊴ respectingEsuch that the induced structure is isomorphic to${\cal L}$. Thus, one can consider the class of all linearly ordered sets that are realized by$\omega /E$; formally,${\cal K}\left = \left\{ {{\cal L}\,|\,{\rm{the}}\,{\rm{order}}\, - \,{\rm{type}}\,{\cal L}\,{\rm{is}}\,{\rm{realized}}\,{\rm{by}}\,E} \right\}$. In this paper we study the relationship between computability-theoretic properties ofEand algebraic properties of linearly ordered sets realized (...) byE. One can also define the following pre-order$ \le _{lo} $on the class of all c.e. equivalence relations:$E_1 \le _{lo} E_2 $if every linear order realized byE1is also realized byE2. Following the tradition of computability theory, thelo-degrees are the classes of equivalence relations induced by the pre-order$ \le _{lo} $. We study the partially ordered set oflo-degrees. For instance, we construct various chains and anti-chains and show the existence of a maximal element among thelo-degrees. (shrink)

Linear Syntax makes a case for a critical reassessment of the wide-spread view that syntax can be reduced to tree structures. It argues that a crucial part of the description of German clausal syntax should instead be based on concepts that are defined in terms of linear order. By connecting the descriptive tools of modern phrase-structure grammar with traditional descriptive scholarship, Andreas Kathol offers a new perspective on many long-standing problems in syntactic theory.

Variants of classical linear logics are presented based on the modal version of new structural rule !?mingle instead of the known rules !weakening and ?weakening. The cut-elimination theorems, the completeness theorems and a characteristic property named the mix separation principle are proved for these logics.

Hypersequent calculus, developed by A. Avron, is one of the most interesting proof systems suitable for nonclassical logics. Although HC has rather simple form, it increases significantly the expressive power of standard sequent calculi. In particular, HC proved to be very useful in the field of proof theory of various nonclassical logics. It may seem surprising that it was not applied to temporal logics so far. In what follows, we discuss different approaches to formalization of logics of linear frames (...) and provide a cut-free HC formalization ofKt4.3, the minimal temporal logic of linear frames, and some of its extensions. The novelty of our approach is that hypersequents are defined not as finite sets but as finite lists of ordinary sequents. Such a solution allows both linearity of time flow, and symmetry of past and future, to be incorporated by means of six temporal rules. Extensions of the basic calculus with simple structural rules cover logics of serial and dense frames. Completeness is proved by Schütte/Hintikka-style argument using models built from saturated hypersequents. (shrink)

The paper studies the logic TL(NBox+-wC) – logic of discrete linear time with current time point clusters. Its language uses modalities Diamond+ (possible in future) and Diamond- (possible in past) and special temporal operations, – Box+w (weakly necessary in future) and Box-w (weakly necessary in past). We proceed by developing an algorithm recognizing theorems of TL(NBox+-wC), so we prove that TL(NBox+-wC) is decidable. The algorithm is based on reduction of formulas to inference rules and converting the rules in special (...) reduced normal form, and, then, on checking validity of such rules in models of singleexponential size in the rules. Also we consider the admissibility problem for TL(NBox+-wC) and show how to reduce the problem for admissibility to the decidability of TL(NBox+-wC) itself using definable universal modalities. (shrink)

The λσ-calculus adds explicit substitutions to the λ-calculus so as to provide a theoretical framework within which the implementation of functional programming languages can be studied. This paper generalises the λσ-calculus to provide a linear calculus of explicit substitutions, called xDILL, which analogously describes the implementation of linear functional programming languages.Our main observation is that there are non-trivial interactions between linearity and explicit substitutions and that xDILL is therefore best understood as a synthesis of its underlying logical structure (...) and the technology of explicit substitutions. This is in contrast to the λσ-calculus where the explicit substitutions are independent of the underlying logical structure. (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 consider certain linear orders with a function on them, and discuss for which types of functions the resulting structure is or is not computably categorical. Particularly, we consider computable copies of the rationals with a fixed-point free automorphism, and also ω with a non-decreasing function.

Linear logic, introduced by Girard, is a refinement of classical logic with a natural, intrinsic accounting of resources. This accounting is made possible by removing the ‘structural’ rules of contraction and weakening, adding a modal operator and adding finer versions of the propositional connectives. Linear logic has fundamental logical interest and applications to computer science, particularly to Petri nets, concurrency, storage allocation, garbage collection and the control structure of logic programs. In addition, there is a direct correspondence between (...) polynomial-time computation and proof normalization in a bounded form of linear logic. In this paper we show that unlike most other propositional logics, full propositional linear logic is undecidable. Further, we prove that without the modal storage operator, which indicates unboundedness of resources, the decision problem becomes PSPACE-complete. We also establish membership in NP for the multiplicative fragment, NP-completeness for the multiplicative fragment extended with unrestricted weakening, and undecidability for fragments of noncommutative propositional linear logic. (shrink)

The logical structure derived from the algebra of generalised projection operators on a module is investigated. With the assumption of the operators being linear, the associated logic becomes Boolean, while without the assumption, the logic does not admit negation: the concept of linearity of projection operators on a module corresponds to that of negation in Boolean logic. The logic of nonlinear operators is formalised and its soundness and completeness results are proved.

This paper addresses a phenomenon in which certain word-parts can be omitted. The evidence shows that the full range of data cannot be captured by a sublexical analysis, since the phenomena can be observed both in phrasal and in lexical environments. It is argued that a form of deletion is involved, and that the phenomena—lexical or otherwise—are subject to the same phonological, semantic, and syntactic constraints. In the formalization that is proposed, all of the above constraints are cast in a (...) parallel and declarative fashion, in the framework of Head-Driven Phrase Structure Grammar (Pollard and Sag Head-driven phrase structure grammar, 1994), since the various levels of linguistic description are locally and simultaneously available. Building on recent accounts of ellipsis, this paper proposes a unified and general account of word-part ellipsis and phrasal ellipsis. (shrink)

Numerous results about capturing complexity classes of queries by means of logical languages work for ordered structures only, and deal with non-generic, or order-dependent, queries. Recent attempts to improve the situation by characterizing wide classes of finite models where linear order is definable by certain simple means have not been very promising, as certain commonly believed conjectures were recently refuted (Dawar's Conjecture). We take on another approach that has to do with normalization of a given order (rather than (...) with defining a linear order from scratch). To this end, we show that normalizability of linear order is a strictly weaker condition than definability (say, in the least fixpoint logic), and still allows for extending Immerman-Vardi-style results to generic queries. It seems to be the weakest such condition. We then conjecture that linear order is normalizable in the least fixpoint logic for any finitely axiomatizable class of rigid structures. Truth of this conjecture, which is a strengthened version of Stolboushkin's conjecture, would have the same practical implications as Dawar's Conjecture. Finally, we suggest a series of reductions of the two conjectures to specialized classes of graphs, which we believe should simplify further work. (shrink)

A complete recursive description of noetherian linear _KL_-algebras is given. _L_-algebras form a quantum structure that occurs in algebraic logic, combinatorial group theory, measure theory, geometry, and in connection with solutions to the Yang-Baxter equation. It is proved that the self-similar closure of a noetherian linear _KL_-algebra is determined by its partially ordered set of primes, and that its elements admit a unique factorization by a decreasing sequence of prime elements.

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)