CS Paper Radar

Abstract computation over first-order structures. Extras: From programs to decision trees I

Christine Gaßner

cs.LO math.LO ·submitted 2026-08-19 12:15 UTC · v1

Abstract

Decisions and their consequences can be described and analyzed by means of decision trees. The decisions themselves depend on questions that, whenever possible, should be answered with yes or no. The original BSS machines over the real numbers are graphs with computation nodes and branching nodes for decisions. The evaluation of BSS machines and algebraic decision trees in computer-aided geometry which have been introduced for various types of numbers generally involves the evaluation of systems of literals of first-order logic. Flowchart-like representations and decision trees are also helpful for analyzing decisions made by BSS RAMs over first-order structures. All algorithms defined by machine-oriented programs of BSS RAMs can be illustrated using flowcharts, walks, and paths in program trees. The basic structures of these tools are graphs and their visual representations can help to characterize the behavior of individual BSS RAMs and other first-order machines. We offer a theoretical framework for linking various models. Here, we introduce program paths and transition systems for transforming partial configurations which are defined syntactically and can be extended and refined later. Finally, we define standard orders for program paths and present algorithms for enumerating finite program paths.

Comment
68 pages, 3 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Succinct Representation of Search Trees on Trees

cs.DS ·2026-09-18 ·Seungbum Jo, Nodari Sitchinava
similarity 0.63
Abstract

A search tree on trees (STT) is a data structure for performing a search for a target vertex in a reference tree. A standard binary search tree is a special case of an STT, where the reference tree is a path of totally ordered elements. In this paper, we study the problem of succinct representation of STTs. We consider two cases: (1) general search trees on trees, and (2) Steiner-closed search trees on trees [Bose et al. TALG 2023]. For both cases, we present representations that can be constructed in polynomial time and achieve optimal space up to the lower-order additive terms. We also present data structures for supporting fast traversals of both general and Steiner-closed STTs. For general STTs our data structure still takes optimal space up to lower-order additive terms.

0.20

A Geometric Derivation of the Bitner--Ehrlich--Reingold Loopless Gray Code Algorithm

cs.DS ·2026-08-24 ·Andrew Au
similarity 0.59
Abstract

The Bitner--Ehrlich--Reingold algorithm generates the binary reflected Gray code with constant work per codeword, using a focus-pointer array. Its compact update is easy to state but gives little indication of why such pointers should exist. This note reconstructs a geometric route to the algorithm. The sequence of flipped bit positions is the ruler sequence, OEIS A007814. We realize its finite prefixes as in-order traversals of recursively expanding trees, decorate each activation with its nearest ancestor to the right, contract all stack operations between successive outputs into successor jumps, and prepare the bounded level-indexed stack by predicting its future slot values. This gives and proves a branch-based loopless generator. The construction grew from an earlier informal public exposition by the author. Viewing horizontal position in the tree as time then explains each stack-slot write as a prediction for the next activation at the same level. Finally, the two possible future roles---an inherited continuation for a right child and a default continuation for a left child---are scheduled together, leading to the two assignments of the published focus-pointer algorithm. The account is a reconstructed derivation, not a claim about the historical reasoning of Bitner, Ehrlich, or Reingold.

0.20

Tree Databases

cs.DB ·2026-09-03 ·Nicolas Spyratos
similarity 0.59
Abstract

We propose a novel database model whose basic structure is a labeled, directed tree with node identities. Intuitively, the root of the tree is seen as an object (or entity), the non-root nodes as attributes of the object and the semantics of each attribute is represented by the unique path leading from the root to the attribute. We define a tree database to be a set of such trees. The trees of the database can be combined to produce new trees using a set of operations on trees that we define in the paper. The query language of our model offers two types of queries, traversal queries and analytic queries. A query (whether traversal or analytic) is always defined over a tree, which is either a tree in the database or a tree derived from other trees using tree operations. The operations on trees and the query language are both defined using a simple functional algebra whose operations are: restriction of a function, composition of functions, pairing of functions and Cartesian product of sets. A distinctive feature of our model is that traversal queries and analytic queries are both defined within the same formal framework; and in fact, traversal queries serve as the building blocks for analytic queries. This is in sharp contrast to the relational model, where analytic queries are defined outside the relational algebra, in the form of SQL Group-by queries. Therefore our model supports data access and data analysis within the same formal framework. We demonstrate the expressive power of our model by showing: (a) how our model can support inheritance in a seamless manner, (b) how one can define consistent relational databases on top of a tree database - with the tree database playing the role of an underlying semantic layer and (c) how a tree database can be used as a user-friendly interface for accessing and analyzing relational data.

0.46

SAT-based Encodings for Optimal Decision Trees with Explicit Paths

cs.LO ·2026-08-20 ·Mikoláš Janota, António Morgado
top venuehighly cited similarity 0.58
Abstract

Decision trees play an important role both in Machine Learning and Knowledge Representation. They are attractive due to their immediate interpretability. In the spirit of Occam's razor, and interpretability, it is desirable to calculate the smallest tree. This, however, has proven to be a challenging task and greedy approaches are typically used to learn trees in practice. Nevertheless, recent work showed that by the use of SAT solvers one may calculate the optimal size tree for real-world benchmarks. This paper proposes a novel SAT-based encoding that explicitly models paths in the tree, which enables us to control the tree's depth as well as size. At the level of individual SAT calls, we investigate splitting the search space into tree topologies. Our tool outperforms the existing implementation. But also, the experimental results show that minimizing the depth first and then minimizing the number of nodes enables solving a larger set of instances.

0.68

Whiel: A Neurosymbolic Platform for Certified Relational Program Verification

cs.DB cs.AIcs.LO ·2026-11-03 ·Jesse Comer, Fangzhu Shen, Shuo Zhang, Mayur Naik, Sudeepa Roy +1 more
benchmarktheory similarity 0.58
Abstract

We present the Whiel (a contraction of Whi(le-R)el) system for Lean-certified reasoning about imperative relational programs. The system can encode containment and equivalence problems for Datalog, its extensions with negation, and the core fragment of graph query languages. It can also represent optimized or incremental evaluation algorithms that are not expressible in the original query language, as well as first-order specifications of integrity constraints, schema mappings, and views arising in data integration, exchange, and sharing. Whiel's program states are database instances, and its imperative structure enables compositional Hoare-style reasoning with first-order relational specifications, using prophecy variables and leveled invariants to support inductive arguments. Whiel supports neurosymbolic discovery of loop invariants whose verification conditions can be checked using the Vampire first-order theorem prover. Counterexamples are fed back into the neurosymbolic pipeline, while proposed solutions are translated into Lean proof certificates. To validate the Whiel system, we evaluate its performance on a curated benchmark suite. In summary, we envision the Whiel system as a tool for tackling mathematically demanding, typically undecidable problems involving complex query and constraint languages, with a high degree of trust in its output.

0.24

Monodromy Computation Model

cs.CC cs.LO ·2026-11-03 ·Xiaoyang Liu
theory similarity 0.57
Abstract

A closed path can return to its starting point while analytic continuation reaches another branch. We construct a finite computational calculus in which retained logarithmic branches supply memory, analytic observations select operations, and descent through a covering exposes deeper memory. Three branch coordinates suffice, and every finite observation uses the same cubic power covering. Each program defines a globally real analytic return map whose integer-lattice execution is realized by actual path lifting. Our first theorem simulates every finite-alphabet, finite-control Post--Turing machine, preserving complete configurations, halting, and divergence. Our second theorem identifies the partial numeric functions of the calculus, under fixed primitive-recursive input and output maps, with exactly the partial recursive functions. Deleting descent leaves a Forward language with a syntax-derived finite observation quotient and a primitive-recursive halting predicate. This yields a strict separation within the calculus and identifies access to deeper memory as its decisive additional operation. The constructions and semantic correspondences are formalized in Lean 4 with Mathlib.

0.18

Type-Directed Discretization of Probabilistic Programs (Extended Version)

cs.PL ·2026-08-17 ·Katherine Wu, Jules Jacobs, Kevin Batz, Alexandra Silva
published similarity 0.57
Abstract · Extended version of OOPSLA'26 paper (with appendices)

We study exact discretization as a semantics-preserving transformation for recursive, higher-order probabilistic programs with continuous distributions. We target programs where continuous values are compared against finitely many constants, so exact inference reduces to a discrete problem. Our central technical contribution is a non-local, type-directed analysis that infers where continuous values can be partitioned into finitely many observationally relevant regions, then rewrites sampling and comparison behavior over those regions. We call this transformation Slice. Because this construction is global and type-directed, correctness requires reasoning beyond the local syntax: we formalize the transformation and prove soundness for boolean queries using a coupling-style logical relations argument over operational semantics. As an application, transformed programs can be executed by discrete engines such as Dice, Roulette, and Storm. Our empirical evaluation shows two complementary strengths of Slice when paired with discrete backends: it enables exact inference for challenging continuous programs that lie beyond the reach of previous exact systems, and, on benchmarks where direct comparison is possible, it is competitive with state-of-the-art exact inference systems for continuous programs.

0.23

DueList: A Theory of Lists with Combinators for SMT Solvers

cs.PL ·2026-09-24 ·Pierre Goutagny, Aymeric Fromherz, Raphaël Monat
hot direction similarity 0.57
Abstract · Revised from Q1 2026 submission

Formal verification tools commonly rely on SMT solvers to automatically reason about programs, leveraging a range of logical theories, e.g., linear integer arithmetic, arrays, or strings, to encode program constructs and verification conditions. Despite recent advances, such solvers still struggle when reasoning about recursive data structures such as lists, which are pervasive in modern functional languages. Additionally, lists are commonly used in conjunction with higher-order combinators to, e.g., generically apply a function to all elements of the list. In this work, we provide first-class support for reasoning about lists within SMT solvers. We focus on lists of arbitrary size that, following the map-reduce paradigm, can be manipulated exclusively through a set of abstract combinators. To this end, we introduce DueList, an abstraction-refinement approach geared towards list reasoning, which we implement on top of off-the-shelf SMT solvers. To evaluate the efficiency of our approach, we assemble a diverse set of 752 benchmarks curated from previous works and real-world programs, and compare DueList against state-of-the-art solvers such as Z3 and CVC5. Our experimental evaluation shows that DueList extends reasoning facilities of existing solvers, allowing to conclude about the (un)satisfiability of a larger range of problems, while outperforming existing solvers in the vast majority of previously supported cases.

0.30