cs.SC

17 posts

arXiv:2411.16348v2 Announce Type: replace Abstract: Formal verification techniques based on computer algebra have proven highly effective for circuit verification. The circuit, given as an and-inverter graph, is encoded as a set of polynomials that automatically generates a Gr\"obner basis with respect to a lexicographic term ordering. Correctness of the circuit can be derived by computing the polynomial remainder of the specification. However, the main obstacle is the monomial blow-up during the rewriting of the specification, which leads to the development of dedicated heuristics to overcome this issue. In this paper, we investigate an orthogonal approach and focus the computational effort on rewriting the Gr\"obner basis itself. Our goal is to ensure the basis contains linear polynomials that can be effectively used to rewrite the linearized specification. We first prove the soundness and completeness of this technique and then demonstrate its practical application. Our implementation of this method shows promising results on benchmarks related to multiplier verification.

Daniela Kaufmann, J\'er\'emy Berthomieu1/22/2025

arXiv:2501.07123v1 Announce Type: cross Abstract: Machine learning is rapidly making its path into natural sciences, including high-energy physics. We present the first study that infers, directly from experimental data, a functional form of fragmentation functions. The latter represent a key ingredient to describe physical observables measured in high-energy physics processes that involve hadron production, and predict their values at different energy. Fragmentation functions can not be calculated in theory and have to be determined instead from data. Traditional approaches rely on global fits of experimental data using a pre-assumed functional form inspired from phenomenological models to learn its parameters. This novel approach uses a ML technique, namely symbolic regression, to learn an analytical model from measured charged hadron multiplicities. The function learned by symbolic regression resembles the Lund string function and describes the data well, thus representing a potential candidate for use in global FFs fits. This study represents an approach to follow in such QCD-related phenomenology studies and more generally in sciences.

Nour Makke, Sanjay Chawla1/14/2025

arXiv:2501.06707v1 Announce Type: new Abstract: ELIZA, created by Joseph Weizenbaum at MIT in the early 1960s, is usually considered the world's first chatbot. It was developed in MAD-SLIP on MIT's CTSS, the world's first time-sharing system, on an IBM 7094. We discovered an original ELIZA printout in Prof. Weizenbaum's archives at MIT, including an early version of the famous DOCTOR script, a nearly complete version of the MAD-SLIP code, and various support functions in MAD and FAP. Here we describe the reanimation of this original ELIZA on a restored CTSS, itself running on an emulated IBM 7094. The entire stack is open source, so that any user of a unix-like OS can run the world's first chatbot on the world's first time-sharing system.

Rupert Lane, Anthony Hay, Arthur Schwarz, David M. Berry, Jeff Shrager1/14/2025

arXiv:2501.06699v1 Announce Type: new Abstract: Much has been discussed about how Large Language Models, Knowledge Graphs and Search Engines can be combined in a synergistic manner. A dimension largely absent from current academic discourse is the user perspective. In particular, there remain many open questions regarding how best to address the diverse information needs of users, incorporating varying facets and levels of difficulty. This paper introduces a taxonomy of user information needs, which guides us to study the pros, cons and possible synergies of Large Language Models, Knowledge Graphs and Search Engines. From this study, we derive a roadmap for future research.

Aidan Hogan, Xin Luna Dong, Denny Vrande\v{c}i\'c, Gerhard Weikum1/14/2025

arXiv:2501.03837v1 Announce Type: new Abstract: We adapt the theory of normal and special polynomials from symbolic integration to the summation setting, and then built up a general framework embracing both the usual shift case and the q-shift case. In the context of this general framework, we develop a unified reduction algorithm, and subsequently a creative telescoping algorithm, applicable to both hypergeometric terms and their q-analogues. Our algorithms allow to split up the usual shift case and the q-shift case only when it is really necessary, and thus instantly reveal the intrinsic differences between these two cases. Computational experiments are also provided.

Shaoshi Chen, Hao Du, Yiman Gao, Hui Huang, Ziming Li1/8/2025

arXiv:2501.03381v1 Announce Type: new Abstract: Complex systems are characterized by nonlinear dynamics, multi-level interactions, and emergent collective behaviors. Traditional analyses that focus solely on pairwise interactions often oversimplify these systems, neglecting the higher-order interactions critical for understanding their full collective dynamics. Recent advances in multivariate information theory provide a principled framework for quantifying these higher-order interactions, capturing key properties such as redundancy, synergy, shared randomness, and collective constraints. However, two major challenges persist: accurately estimating joint entropies and addressing the combinatorial explosion of interacting terms. To overcome these challenges, we introduce THOI (Torch-based High-Order Interactions), a novel, accessible, and efficient Python library for computing high-order interactions in continuous-valued systems. THOI leverages the well-established Gaussian copula method for joint entropy estimation, combined with state-of-the-art batch and parallel processing techniques to optimize performance across CPU, GPU, and TPU environments. Our results demonstrate that THOI significantly outperforms existing tools in terms of speed and scalability. For larger systems, where exhaustive analysis is computationally impractical, THOI integrates optimization strategies that make higher-order interaction analysis feasible. We validate THOI accuracy using synthetic datasets with parametrically controlled interactions and further illustrate its utility by analyzing fMRI data from human subjects in wakeful resting states and under deep anesthesia. Finally, we analyzed over 900 real-world and synthetic datasets, establishing a comprehensive framework for applying higher-order interaction (HOI) analysis in complex systems.

Laouen Belloli, Pedro Mediano, Rodrigo Cofr\'e, Diego Fernandez Slezak, Rub\'en Herzog1/8/2025

arXiv:2101.03482v3 Announce Type: replace-cross Abstract: We define a new type of ideal basis called the proper basis that improves both Gr\"obner basis and Buchberger's algorithm. Let $x_1$ be the least variable of a monomial ordering in a polynomial ring $K[x_1,\dotsc,x_n]$ over a field $K$. The Gr\"obner basis of a zero-dimensional polynomial ideal contains a univariate polynomial in $x_1$. The proper basis is defined and computed in the variables $\tilde{\bm{x}}:=(x_2,\dotsc,x_n)$ with $x_1$ serving as a parameter in the algebra $K[x_1][\tilde{\bm{x}}]$. Its algorithm is more efficient than not only Buchberger's algorithm whose elimination of $\tilde{\bm{x}}$ unnecessarily involves the least variable $x_1$ but also M\"oller's algorithm due to its polynomial division mechanism. This is corroborated by a series of benchmark testings herein. The proper basis is in a modular form and neater than Gr\"obner basis and hence reduces its coefficient swell problem. It is expected that all the state of the art algorithms improving Buchberger's algorithm over the last decades can be further improved if we apply them to the proper basis.

Sheng-Ming Ma1/6/2025

arXiv:2501.00563v1 Announce Type: cross Abstract: We present a new Python package called "motives", a symbolic manipulation package based on SymPy capable of handling and simplifying motivic expressions in the Grothendieck ring of Chow motives and other types of $\lambda$-rings. The package is able to manipulate and compare arbitrary expressions in $\lambda$-rings and, in particular, it contains explicit tools for manipulating motives of several types of commonly used moduli schemes and moduli stacks of decorated bundles on curves. We have applied this new tool to advance in the verification of Mozgovoy's conjectural formula for the motive of the moduli space of twisted Higgs bundles, proving that it holds in rank 2 and 3 for any curve of genus up to 18 and any twisting bundle of small degree.

Daniel Sanchez, David Alfaya, Jaime Pizarroso1/3/2025

arXiv:2501.00364v1 Announce Type: new Abstract: Reward machines (RMs) are an effective approach for addressing non-Markovian rewards in reinforcement learning (RL) through finite-state machines. Traditional RMs, which label edges with propositional logic formulae, inherit the limited expressivity of propositional logic. This limitation hinders the learnability and transferability of RMs since complex tasks will require numerous states and edges. To overcome these challenges, we propose First-Order Reward Machines ($\texttt{FORM}$s), which use first-order logic to label edges, resulting in more compact and transferable RMs. We introduce a novel method for $\textbf{learning}$ $\texttt{FORM}$s and a multi-agent formulation for $\textbf{exploiting}$ them and facilitate their transferability, where multiple agents collaboratively learn policies for a shared $\texttt{FORM}$. Our experimental results demonstrate the scalability of $\texttt{FORM}$s with respect to traditional RMs. Specifically, we show that $\texttt{FORM}$s can be effectively learnt for tasks where traditional RM learning approaches fail. We also show significant improvements in learning speed and task transferability thanks to the multi-agent learning framework and the abstraction provided by the first-order language.

Leo Ardon, Daniel Furelos-Blanco, Roko Para\'c, Alessandra Russo1/3/2025

arXiv:2412.18143v1 Announce Type: new Abstract: Graphs are the most suitable structures for modeling objects and interactions in applications where component inter-connectivity is a key feature. There has been increased interest in graphs to represent domains such as social networks, web site link structures, and biology. Graph stores recently rose to prominence along the NoSQL movement. In this work we will focus on NOSQL graph databases, describing their peculiarities that sets them apart from other data storage and management solutions, and how they differ among themselves. We will also analyze in-depth two different graph database management systems - AllegroGraph and Neo4j that uses the most popular graph models used by NoSQL stores in practice: the resource description framework (RDF) and the labeled property graph (LPG), respectively.

Veronica Santos, Bruno Cuconato12/25/2024

arXiv:2412.18294v1 Announce Type: new Abstract: This paper presents an advanced method for addressing the inverse kinematics and optimal path planning challenges in robot manipulators. The inverse kinematics problem involves determining the joint angles for a given position and orientation of the end-effector. Furthermore, the path planning problem seeks a trajectory between two points. Traditional approaches in computer algebra have utilized Gr\"obner basis computations to solve these problems, offering a global solution but at a high computational cost. To overcome the issue, the present authors have proposed a novel approach that employs the Comprehensive Gr\"obner System (CGS) and CGS-based quantifier elimination (CGS-QE) methods to efficiently solve the inverse kinematics problem and certify the existence of solutions for trajectory planning. This paper extends these methods by incorporating smooth curves via cubic spline interpolation for path planning and optimizing joint configurations using shortest path algorithms to minimize the sum of joint configurations along a trajectory. This approach significantly enhances the manipulator's ability to navigate complex paths and optimize movement sequences.

Yusuke Shirato, Natsumi Oka, Akira Terui, Masahiko Mikawa12/25/2024

arXiv:2411.00031v2 Announce Type: replace Abstract: Solving algebra problems (APs) continues to attract significant research interest as evidenced by the large number of algorithms and theories proposed over the past decade. Despite these important research contributions, however, the body of work remains incomplete in terms of theoretical justification and scope. The current contribution intends to fill the gap by developing a review framework that aims to lay a theoretical base, create an evaluation scheme, and extend the scope of the investigation. This paper first develops the State Transform Theory (STT), which emphasizes that the problem-solving algorithms are structured according to states and transforms unlike the understanding that underlies traditional surveys which merely emphasize the progress of transforms. The STT, thus, lays the theoretical basis for a new framework for reviewing algorithms. This new construct accommodates the relation-centric algorithms for solving both word and diagrammatic algebra problems. The latter not only highlights the necessity of introducing new states but also allows revelation of contributions of individual algorithms obscured in prior reviews without this approach.

Xinguo Yu, Weina Cheng, Chuanzhi Yang, Ting Zhang12/24/2024

arXiv:2412.16161v1 Announce Type: new Abstract: In this short article I introduce the evitaicossa package which provides functionality for antiassociative algebras in the R programming language; it is available on CRAN at https://CRAN.R-project.org/package=evitaicossa.

Robin K. S. Hankinn12/24/2024

arXiv:2412.17280v1 Announce Type: new Abstract: This study presents a comprehensive mathematical framework for modeling the flight dynamics of a six-degree-of-freedom fixed-wing aircraft as a rigid body with three control surfaces: rudder, elevators, and ailerons. The framework consists of 35 differential-algebraic equations (DAEs) and requires 30 constants to be specified. It supports both direct and inverse flight dynamics analyses. In direct dynamics, the historical profiles of control inputs (deflection angles and engine thrust) are specified, and the resulting flight trajectory is predicted. In inverse dynamics, the desired flight trajectory and an additional constraint are specified to determine the required control inputs. The framework employs wind axes for linear-momentum equations and body axes for angular-momentum equations, incorporates two flight path angles, and provides formulas for aerodynamic force and moment coefficients. Key advantages include improved computational efficiency, elimination of Euler angle singularities, and independence from symmetry assumptions with regard to the aircraft's moments of inertia. The model also accounts for nonlinear air density variations with altitude, up to 20 km above mean sea level, making it suitable for accurate and efficient flight dynamics simulations.

Osama A. Marzouk12/24/2024

arXiv:2412.17336v1 Announce Type: new Abstract: Knowledge graphs (KGs), which store an extensive number of relational facts, serve various applications. Recently, personalized knowledge graphs (PKGs) have emerged as a solution to optimize storage costs by customizing their content to align with users' specific interests within particular domains. In the real world, on one hand, user queries and their underlying interests are inherently evolving, requiring PKGs to adapt continuously; on the other hand, the summarization is constantly expected to be as small as possible in terms of storage cost. However, the existing PKG summarization methods implicitly assume that the user's interests are constant and do not shift. Furthermore, when the size constraint of PKG is extremely small, the existing methods cannot distinguish which facts are more of immediate interest and guarantee the utility of the summarized PKG. To address these limitations, we propose APEX$^2$, a highly scalable PKG summarization framework designed with robust theoretical guarantees to excel in adaptive summarization tasks with extremely small size constraints. To be specific, after constructing an initial PKG, APEX$^2$ continuously tracks the interest shift and adjusts the previous summary. We evaluate APEX$^2$ under an evolving query setting on benchmark KGs containing up to 12 million triples, summarizing with compression ratios $\leq 0.1\%$. The experiments show that APEX outperforms state-of-the-art baselines in terms of both query-answering accuracy and efficiency.

Zihao Li, Dongqi Fu, Mengting Ai, Jingrui He12/24/2024

arXiv:2412.17099v1 Announce Type: cross Abstract: A finite group with an integral representation has two induced canonical actions, one on polynomials and one on Laurent polynomials. Knowledge about the invariants is in either case applied in many computations by means of symmetry reduction techniques, for example in algebraic systems solving or optimization. In this article, we realize the two actions as the additive action on the symmetric algebra and the multiplicative action on the group algebra of a lattice with Weyl group symmetry. By constructing explicit equivariant isomorphisms, we draw algorithmic relations between the two, which allow the transfer and preservation of representation- and invariant-theoretic properties. Our focus lies on the multiplicative coinvariant space, which is identified with the regular representation and harmonic polynomials.

Sebastian Debus, Tobias Metzlaff12/24/2024

arXiv:2412.15829v1 Announce Type: new Abstract: Large knowledge graphs capture information of a large number of entities and their relations. Among the many relations they capture, class subsumption assertions are usually present and expressed using the \texttt{rdfs:subClassOf} construct. From our examination, publicly available knowledge graphs contain many potentially erroneous cyclic subclass relations, a problem that can be exacerbated when different knowledge graphs are integrated as Linked Open Data. In this paper, we present an automatic approach for resolving such cycles at scale using automated reasoning by encoding the problem of cycle-resolving to a MAXSAT solver. The approach is tested on the LOD-a-lot dataset, and compared against a semi-automatic version of our algorithm. We show how the number of removed triples is a trade-off against the efficiency of the algorithm.

Shuai Wang, Peter Bloem, Joe Raad, Frank van Harmelen12/23/2024