archive
Every paper Pith has read. Search by title, abstract, or pith.
213 papers in cs.FL · page 2
-
Hyper-minimization is decidable for well-typed register automata
Hyper-Minimization for Deterministic Register Automata
-
Compiled forms enable direct projection for quantifiers in alternating automata
Knowledge Compilation for Quantification in Alternating Automata
-
NFA square roots require up to n cubed states
Nondeterministic state complexity of square root
-
Turing machine extension defines context-awareness
On defining and modeling context-awareness
-
Interactive agents clarify vague specs before STL generation
ClarifySTL: An Interactive LLM Agent Framework for STL Transformation through Requirements Clarification
-
Greedy dueling sequence converges to Thue-Morse at specific rate
The speed of convergence in greedy Galois games
-
String diagrams axiomatize behavioral distances for nondeterministic processes
A Diagrammatic Axiomatisation of Behavioural Distance of Nondeterministic Processes
-
Four-symbol coding gives bijection between words and pedal triangles
Primitive Two-Dimensional Words and Iterated Pedal Triangles via Symbolic Coding
-
These lecture notes survey automata-theoretic
Runtime Verification: Monitoring, Knowledge, and Uncertainty (Lecture Notes)
-
Regular languages split into constant or logarithmic FO rank growth
Finite-Horizon First-Order Rank Profiles of Regular Languages
-
Hesitant tree automata match first-order logic on infinite trees
Automaton-based Characterisations of First Order Logic over Infinite Trees
-
Fixed-parameter graph languages identifiable in the limit
Distributional Learning of Graph Languages Generated by Fixed-Interface Clause Systems
-
Tortoise and hare rules extend abelian complexity to infinite words
Subword enumeration up to stack-sorting equivalence
-
Lecture notes map verification of neural networks
Verification of Neural Networks (Lecture Notes)
-
Every positional ω-regular property fits inside LTL
Positional Properties in Temporal Logic
-
Ideal automata split into smaller intersection components in poly time
Decomposition of Automata recognizing Ideals
-
Transducer output Hamming distance check is NL-complete for fixed k
Hamming distance between finite transducers
-
Lower bounds computed for reachability in random-clock automata
Minimum Reachability Probabilities in Rectangular Automata with Random Clocks
-
HOA emptiness is NP-complete for every acceptance condition
A Theory of Hanoi Omega-Automata and Games
-
Regular grammars give singly-exponential recognizers for SP graphs
Regular Grammars as Effective Representations of Recognizable Sets of Series-Parallel Graphs
-
SemML 2.0 solves more LTL synthesis problems faster than rivals
SemML 2.0: Synthesizing Controllers for LTL
-
VAS reachability improves to F_{d-2} bound from F_d
Improving Reachability in Vector Addition Systems through Pumpability
-
AI theorem generators compile but pass only 39% semantic tests
Benchmarking Testing in Automated Theorem Proving
-
Local algebraic checks decide Eve-positionality for omega-regular languages
An algebraic characterisation of Eve-positional languages
-
Word problem is visibly pushdown only for finite groups
Visibly Pushdown Languages in Groups
-
N-gram promotion ensembles match neural accuracy at lower cost
Promoting Simple Agents: Ensemble Methods for Event-Log Prediction
-
Algorithm learns state machines with registers and guards
Active Inference of Extended Finite State Machine Models with Registers and Guards
-
The paper shows that prefix parsing reduces to ordinary parsing by transforming any…
Prefix Parsing is Just Parsing
-
Minimal evidence visualization explains CTL satisfaction and violations
Visualising CTL Witnesses and Counterexamples -- Extended Version
-
Forbidden context and order collapse CDGS to five classical classes
Forbidden-Context & Ordered Grammar Systems
-
Binary languages define all graphs via word patterns
On Languages Describing Large Graph Classes
-
Automata-defined CSPs inherit Boolean dichotomy theorem
Automatic constraint satisfaction problem
-
LTLf+ obligations synthesize in linear time from weak automata
Symbolic Synthesis for LTLf+ Obligations
-
Weighted automata model financial payoffs under uncertainty
Weighted Automata and Regular Expressions for Financial Systems
-
Fungal automata prediction is P-complete for majority rule at radius 1.5
Complexity of Fungal Automaton Prediction
-
Graded checks find protocol failures missed by binary verification
Graded Symbolic Verification with a Fuzzy Dolev-Yao Attacker Model
-
Game of Life patches become programmable semigroups
Measuring the Computational Power of Finite Patches of Cellular Automata
-
The paper develops new techniques for embedding word structures from Euclidean Bianchi…
On Word Representations and Embeddings in Complex Matrices
-
Agent language lets extensions run safely inside verified bounds
CBCL: Safe Self-Extending Agent Communication
-
Normality iff automaton gamblers' capital converges exponentially
Characterizing normality via automata and random matrix products
-
Higher-order polyregular equivalence is undecidable
Polyregular equivalence is undecidable in higher-order types
-
Bimachine bijection minimizes registers of string transducers in polynomial time
Minimizing Streaming String Transducers: An algebraic approach
-
Fixed positive sites fix uniform coset probabilities for CA measures
On a Constraint on Invariant Measures of Certain Cellular Automata
-
LLM creates alias-free model for Petri-net concurrency verification
CIR+CVN: Bridging LLM Semantic Understanding and Petri-Net Verification for Concurrent Programs
-
State trajectories alone suffice to learn reward machines
Active Reward Machine Inference From Raw State Trajectories
-
Quantum automata need exactly Θ(n²) classical states for exact simulation
The Quadratic State Cost of Classical Simulation of One-Way Quantum Finite Automata
-
k-sliced reorderings yield constant-space predictive monitors
Parametrizing Reads-From Equivalence for Predictive Monitoring
-
Symbolic states yield compact reachability graph for Petri net product lines
Efficient Construction of Reachability Graphs for Petri Net Product Lines
-
PTPNs model supply chain timing by tracking manager as mobile resource
Modelling and Analysis of Supply Chains using Product Time Petri Nets
-
Minimal DSL compiles to C monitors cutting MAVLink latency by 4x
From High-Level Types to Low-Level Monitors: Synthesizing Verified Runtime Checkers for MAVLink