Elementary Flux Modes (EFM) allow the description of the minimal sets of reactions in a metabolic network under steady-state conditions, representing unique and feasible pathways. They fully characterize the solution ...
详细信息
ISBN:
(纸本)9783031716706;9783031716713
Elementary Flux Modes (EFM) allow the description of the minimal sets of reactions in a metabolic network under steady-state conditions, representing unique and feasible pathways. They fully characterize the solution space but a combinatorial explosion prevents their calculation when the network is large. Furthermore, it is not necessary to calculate all of them, as many of them are not biologically relevant. Therefore, the software aspefm, which combines the use of Answer Set programming and Linear programming, proposes to integrate different types of constraints in the EFM computation such as equilibrium constants, Boolean regulatory rules, growth yields and growth medium. The addition of constraints makes it possible to cut off research pathways that lead to non-relevant EFMs. The computation of the EFMs of interest significantly reduces the computational time and saves space. In this article, we have added thermodynamic constraints in terms of the Gibbs energy of reactions, which constrain metabolite concentrations within a chosen interval. This constraint is added as a theory propagator and it reduces the enumeration during the computation. We applied our tool to the central carbon metabolism of E. coli and showed that the Gibbs energy constraints suppress a large number of non-relevant EFMs.
In this paper, we extend the connection between argumentation formalisms and logic programs, by showing the equivalence between bipolar argumentation beta-semantics and various 3-valued logic programming semantics. In...
详细信息
ISBN:
(纸本)9783031790317;9783031790324
In this paper, we extend the connection between argumentation formalisms and logic programs, by showing the equivalence between bipolar argumentation beta-semantics and various 3-valued logic programming semantics. In particular, we show that beta-semi-stable semantics corresponds to L-stable semantics, which has been previously shown not to be expressible by traditional attack-only argumentation frameworks. Besides enhancing our understanding of how logic programs relate to argumentation with support, we provide direct translations between them and their semantics, allowing their interchangeable use.
The restricted logic programming language Datalog has become a popular implementation target for deductive-analytic workloads including social-media analytics and program analysis. Modern Datalog engines compile Datal...
详细信息
The restricted logic programming language Datalog has become a popular implementation target for deductive-analytic workloads including social-media analytics and program analysis. Modern Datalog engines compile Datalog rules to joins over explicit representations of relations-often B-trees or hash maps. While these modern engines have enabled high scalability in many application domains, they have a crucial weakness: achieving the desired algorithmic complexity may be impossible due to representation-imposed overhead of the engine's data structures. In this paper, we present the "Bring Your Own Data Structures" (BYODS) approach, in the form of a DSL embedded in Rust. Using BYODS, an engineer writes logical rules which are implicitly parametric on the concrete data structure representation;our implementation provides an interface to enable "bringing their own" data structures to represent relations, which harmoniously interact with code generated by our compiler (implemented as Rust procedural macros). We formalize the semantics of BYODS as an extension of Datalog's;our formalization captures the key properties demanded of data structures compatible with BYODS, including properties required for incrementalized (semi-naive) evaluation. We detail many applications of the BYODS approach, implementing analyses requiring specialized data structures for transitive and equivalence relations to scale, including an optimized version of the Rust borrow checker Polonius;highly-parallel PageRank made possible by lattices;and a large-scale analysis of LLVM utilizing index-sharing to scale. Our results show that BYODS offers both improved algorithmic scalability (reduced time and/or space complexity) and runtimes competitive with state-of-the-art parallelizing Datalog solvers.
Cascading phenomena in social networks happen when the adoption of some behaviour by initial adopters causes some of their immediate friends to adopt which again causes some of their friends' friends to adopt, and...
详细信息
ISBN:
(纸本)9789819602131;9789819602148
Cascading phenomena in social networks happen when the adoption of some behaviour by initial adopters causes some of their immediate friends to adopt which again causes some of their friends' friends to adopt, and so on. Who the initial adopters are, or rather how they are positioned in the network, is of crucial importance for the potential cascade. In this paper we look at the relative importance of different agents as initial adopters in a network, for a given cascading goal such as a complete cascade: which groups of agents are sufficient, which groups are necessary, and which agents are the most important to have as initial adopters in order for the goal to be achieved? For the latter question, we look to cooperative games and power measures to identify agents who are pivotal for a group of inital adopters with respect to the goal. We characterise the computational complexity of resulting decision and counting problems, when the goal is represented using a propositional logical formula. We also draw connections to abduction in logic programming.
Deciphering gene regulatory networks' functioning is an essential step for better understanding of life, as these networks play a fundamental role in the control of cellular processes. Boolean networks have been w...
详细信息
Deciphering gene regulatory networks' functioning is an essential step for better understanding of life, as these networks play a fundamental role in the control of cellular processes. Boolean networks have been widely used to represent gene regulatory networks. They allow to describe the dynamics of complex gene regulatory networks straightforwardly and efficiently. The attractors are essential in the analysis of the dynamics of a Boolean network. They explain that a particular cell can acquire specific phenotypes that may be transmitted over several generations. In this work, we consider a new representation of Boolean networks' dynamics based on a new semantics used in Answer Set programming (ASP). We use logic programs and ASP to express and deal with gene regulatory networks seen as Boolean networks, and develop a method to detect all the attractors of such networks. We first show how to represent and deal with general Boolean networks for the synchronous and asynchronous updates modes, where the computation of attractors requires a simulation of these networks' dynamics. Then, we propose an approach for the particular case of circular networks where no simulation is needed. This last specific case plays an essential role in biological systems. We show several theoretical properties;in particular, simple attractors of the gene networks are represented by the stable models of the corresponding logic programs and cyclic attractors by its extra-stable models. These extra-stable models correspond to the extra-extensions of the new semantics that are not captured by the semantics of stable models. We then evaluate the proposed approach for general Boolean networks on real biological networks and the one dedicated to the case of circular networks on Boolean networks generated randomly. The obtained results for both approaches are encouraging.
The Semantic Web provides standards for knowledge graphs (KGs), which have become popular for solving data heterogeneity problems in enterprises, since they allow for flexible data modelling and integration via linkin...
详细信息
ISBN:
(纸本)9783031789540;9783031789557
The Semantic Web provides standards for knowledge graphs (KGs), which have become popular for solving data heterogeneity problems in enterprises, since they allow for flexible data modelling and integration via linking of graphs. This flexibility requires standards to ensure data quality and consistent state, such as the Shapes Constraint Language SHACL. However, SHACL does not provide the means to explain why constraint violations occur and how the KG can be repaired to conform to the constraints. Also, repairs for a KG can come with a high number of different alternative choices to pick from, where we need a way to determine preferences in practice. Finally, knowledge in the KG itself can be exploited for repairs to determine fresh values and preferred choices and to identify incorrect data from a real-world perspective. For these challenges, we aim to develop a system that combines logic-based repairs and data-driven analysis for a repair approach that concludes KGs towards a quality fix point. The approach will not only be defined at the formal level, but we also will provide prototypical implementations for practical experiments, thereby positioning it at the intersection of theoretical and applied research. Use cases shall be provided from companies, projects and open data to better understand how repairs can be applied effectively in practice. With this work we contribute to improving the quality of KGs by providing intelligent knowledge graph repair.
We present Rhyme, a declarative multi-paradigm query language designed for querying and transforming nested structures such as JSON, tensors, and beyond. Rhyme is designed to be multi-paradigm from ground-up allowing ...
详细信息
ISBN:
(纸本)9789819722990;9789819723003
We present Rhyme, a declarative multi-paradigm query language designed for querying and transforming nested structures such as JSON, tensors, and beyond. Rhyme is designed to be multi-paradigm from ground-up allowing it to seamlessly accommodate typical data processing operations-ranging from aggregations and group-bys to joins-while also having the versatility to express diverse computations like tensor expressions (a la einops) and declaratively express visualizations (e.g., visualizing query outputs with tables, charts, and so on). Rhyme generates optimized JavaScript code for queries by constructing an intermediate representation that implicitly captures the program structure via dependencies. This paper presents a system description of Rhyme implementation while highlighting key design decisions and various use cases covered by Rhyme.
Specifying and implementing a proof system from scratch requires significant effort. logical Frameworks and Higher Order logic programming Languages provide dedicated, high-level meta languages to facilitate this task...
详细信息
ISBN:
(纸本)9798400709692
Specifying and implementing a proof system from scratch requires significant effort. logical Frameworks and Higher Order logic programming Languages provide dedicated, high-level meta languages to facilitate this task in two ways: 1) variable binding and substitution are for free when meta language binders represent object logic ones;2) proof construction, and proof search, are greatly simplified by leveraging the unification procedure provided by the meta language. Notable examples of meta languages are Elf [21], Twelf [23], lambda Prolog [16], Beluga [24], Abella [8] and Isabelle [31] which have been used to implement or specify many formal systems such as First Order logic [5], Set Theory [20], Higher Order logic [19], and the Calculus of Constructions [4]. The object logic we are interested in is Coq's type theory [28]. We aim to develop a higher-order unification-based proof search procedure using the meta language Elpi [3], a dialect of lambda Prolog. Elpi's equational theory includes beta eta-equivalence and features a higher-order unification procedure similar or equal to(m) for the pattern fragment [15]. Elpi offers an encoding of Coq terms that is suitable for meta programming [6, 9, 26, 27] but that restricts similar or equal to(m) to first-order unification problems only. We refer to this basic encoding as O. In this paper we translate unification problems in O to an alternative encoding called M, from which we derive similar or equal to(O), the higher-order unification procedure of O. similar or equal to(O) honours beta eta-equivalence for terms within the pattern fragment, and allows for the use of heuristics when the terms fall outside the pattern fragment. Moreover, as similar or equal to(O) delegates most of the work to similar or equal to(m), it can be used to efficiently simulate a logic program in O by taking advantage of unification-related optimizations of the meta language, such as clause indexing.
Despite Large Language Models (LLMs) have revolutionised Natural Language Processing (NLP), their capability of performing logical reasoning and automated planning is still debated. In this context, the state of the a...
详细信息
ISBN:
(纸本)9783031711695;9783031711701
Despite Large Language Models (LLMs) have revolutionised Natural Language Processing (NLP), their capability of performing logical reasoning and automated planning is still debated. In this context, the state of the art is PlanGPT, a GPT-2 model specifically trained for planning tasks. This recent approach provides GPT-based planning policies with remarkable performance, but it can generate invalid plans containing violated action preconditions or unsatisfied goals. To address this limitation, we propose an extension of PlanGPT that integrates a plan validator into the generation process. The validator is exploited to prune invalid plan prefixes during the GPT token generation, obtaining a more robust and powerful solution to planning via GPT. We empirically evaluate the effectiveness of our approach and demonstrate its potential in various planning domains.
Recent advances in reinforcement learning (RL) have shown much promise across a variety of applications. However, issues such as scalability, explainability, and Markovian assumptions limit its applicability in certai...
详细信息
ISBN:
(纸本)9798350385359
Recent advances in reinforcement learning (RL) have shown much promise across a variety of applications. However, issues such as scalability, explainability, and Markovian assumptions limit its applicability in certain domains. We observe that many of these shortcomings emanate from the simulator as opposed to the RL training algorithms themselves. As such, we propose a semantic proxy for simulation based on a temporal extension to annotated logic. In comparison with two high-fidelity simulators, we show up to three orders of magnitude speed-up while preserving the quality of policy learned. In addition, we show the ability to model and leverage non-Markovian dynamics and instantaneous actions while providing an explainable trace describing the outcomes of the agent actions.
暂无评论