Given a prime p, we exhibit a Horn sentence H p which expresses "the cardinality is not p" and has size O(p 5 log p).

"Both superb and essential... Succi, with clarity and wit, takes us from quarks and Boltzmann to soft matter - precisely the frontier of physics and life." Stuart Kauffman, MacArthur Fellow, Fellow of the Royal Society of Canada, Gold Medal Accademia Lincea We live in a world of utmost complexity, outside and within us. There are thousand of billions of billions of stars out there in the Universe, a hundred times more molecules in a glass of water, and another hundred times (...) more in our body, all working in sync to keep us alive and well. At face value, such numbers spell certain doom for our ability to make any sense at all of the world around and within us. And yet, they don't. Why, and how - this book endeavours to provide an answer to these questions with specific reference to a selected window of the physics-biology interface. The story unfolds over four main Parts. Part I provides an introduction to the main organizational principles which govern the functioning of complex systems in general, such as nonlinearity, nonlocality and ultra-dimensions. Part II deals with thermodynamics, the science of change, starting with its historical foundations laid down in the 19th century, and then moving on to its modern and still open developments in connection with biology and cosmology. Part III deals with the main character of this book, free energy, and the wondrous scenarios opened up by its merger with the modern tools of statistical physics. It also describes the basic facts about soft matter, the state of matter most relevant to biological organisms. Finally, Part IV discusses the connection between time and complexity, and its profound implications on the human condition, i.e. the one-sided nature of time and the awareness of human mortality. It concludes with a few personal considerations about the special place of emotions and humility in science. (shrink)

We consider the structure of all labeled trees, called also infinite terms, in the first order language with function symbols in a recursive signature of cardinality at least two and at least a symbol of arity two, with equality and a binary relation symbol which is interpreted to be the subtree relation. The existential theory over of this structure is decidable (see Tulipani [9]), but more complex fragments of the theory are undecidable. We prove that the theory of the (...) structure is in , where formulas are those in prenex form consisting of a string of unbounded existential quantifiers followed by a string of arbitrary quantifiers all bounded with respect to . Since the fragment of the theory was already known to be -hard (see Marongiu and Tulipani [5]), it is now established to be -complete. (shrink)

We consider the theoryT IT of infinite terms. The axioms for the theoryT IT are analogous to the Mal'cev's axioms for the theoryT IT of finite terms whose models are the locally free algebras. Recently Maher [Ma] has proved that the theoryT IT in a finite non singular signature plus the Domain Closure Axiom is complete. We give a description of all the complete extension ofT IT from which an effective decision procedure forT IT is obtained. Our approach considers formulas (...) built up with syntactic terms containing pointers. Using such a technique, the analysis of the theoryT IT can be carried out in analogy with Mal'cev's analysis ofT FT. Our results follow from an effective quantifier elimination procedure for formulas with pointers. (shrink)

We introduce a reciprocity criterion for coalition formation among goal-directed agents, which we call the indecomposable do-ut-des property. It refines an older reciprocity property, called the do-ut-des or give-to-get property by considering the fact that agents prefer to form coalitions whose components cannot be formed independently. A formal description of this property is provided as well as an analysis of algorithms and their complexity. We provide an algorithm to decide whether a coalition has the desired property, and we show that (...) the problem to verify whether a single coalition satisfies the property is tractable. Moreover, we provide an algorithm to search all the sub-coalitions of a given coalition satisfying the new property. Even if this problem is not computationally tractable, we show that in several cases, also the complexity of this problem may decrease considerably. (shrink)

Design patterns are generalized solutions to frequently recurring problems. They were initially developed by architects and computer scientists to create a higher level of abstraction for their designs. Here, we extend these concepts to cell biology to lend a new perspective on the evolved designs of cells' underlying reaction networks. We present a catalog of 21 design patterns divided into three categories: creational patterns describe processes that build the cell, structural patterns describe the layouts of reaction networks, and behavioral patterns (...) describe reaction network function. Applying this pattern language to the E. coli central metabolic reaction network, the yeast pheromone response signaling network, and other examples lends new insights into these systems. (shrink)

Computer analysis of biological systems, using approaches such as metabolic control analysis is common. A typical example is a language like Herbert Sauro's SCAMP (Sauro & Fell, 1991), which allows simulations of enzyme systems, and calculation of control coefficients and elasticities. However such systems are motivated by the underlying biochemical theory and often have limitations as programming languages which mean that they can only be applied to particular classes of problems.ABPL (a biochemical programming language) extends these ideas by (...) adding all the facilities of a fully-fledged programming language, together with some of the capabilities of a modern computer algebra system. Syntactically it derives from the programming language LISP, while the underlying functionality is that of iMAP, the successor to SCAMP. (shrink)

In earlier work we have described how computer algebra may be used to derive composite rate laws for complete systems of equations, using the mathematical technique of Gröbner Bases (Bennett, Davenport and Sauro, 1988). Such composite rate laws may then be fitted to experimental data to yield estimates of kinetic parameters.Recently we have been investigating the practical application of this methodology to the estimation of kinetic parameters for the closed two enzyme system of aspartate aminotransferase (AAT) and malate dehydrogenase (...) (MDH) (Fisher 1990a; Fisher 1990b; Bennett and Fisher, 1990). (shrink)