archive
Every paper Pith has read. Search by title, abstract, or pith.
99 papers in cs.FL · page 1
-
Transducers extend stabilization for faster relational string solving
String Solving with Stabilization and Transducers (Technical Report)
-
Nested reset counters hit exact F_Ωk levels
The Complexity of Nested Reset Counter Systems
-
Sampling and model-checking oracles learn regular POMDP policies
Synthesizing POMDP Policies: Sampling Meets Model-checking via Learning
-
Non-uniform cellular automata run on hyperbolic lattices
Universal Design and Physical Applications of Non-Uniform Cellular Automata on Translationally Invariant Lattices
-
Conventions enable composition of policies for multiple omega-regular goals
Decoupled Planning for Multiple Omega-Regular Objectives
-
LLM JSON stays valid inside tight token budgets
TruncProof: A Guardrail for LLM-based JSON Generation under Token-Length Constraints
-
Flattening lets QuAK analyze nested quantitative automata
Extending QuAK with Nested Quantitative Automata
-
Syntactic obligations translate to MTBDD automata for fast synthesis
Fast Obligation Translation and Synthesis
-
Sound rewards let POMDPs meet LTL specs despite fog
Ensuring Logic in the Fog: Sound POMDP Synthesis with LTL Objectives
-
Tool synthesizes reactive systems over infinite integers
sweap: Reactive Synthesis for Infinite-State Integer Problems
-
Sentence-interface types identify bounded-fan-out linear MCFGs from positive data
Finite Sentence-Interface Control for Learning Bounded-Fan-Out Linear MCFGs under Fixed Monoid Typing
-
General criteria guarantee minimal models for streaming transducers
Minimization of Streaming Transducers
-
Streaming transducers admit minimal models
Minimization of Streaming Transducers
-
Quotients of permutation automata attain every positive accepting-state count
A Unary-to-Nonunary Transition in the Accepting-State Spectrum of Right Quotient for Permutation Automata
-
Quantum automata need Θ(n²) states to simulate exactly
On the Simulation Cost of Quantum Finite Automata
-
R-alignment gives bounded-depth forest decompositions
A Factorization Theorem for Forest Algebras
-
Ordered agents let population protocols recognize unambiguous star-free languages
Population Protocols over Ordered Agents
-
Asymptotic Hausdorff turns edit distances into language metrics
Asymptotic Hausdorff and Language Similarity
-
Automata over infinite alphabets can have non-rational Parikh images
Star Complexity of Parikh Images of Languages over Infinite Alphabets
-
Two-variable logic on data words decidable for specific monoids
Set Automata and Limits of Decidability of Two-Variable Logic on Data Words
-
NL separated from logCFL via pebble automata entropy
Entropy of pebble automata and space complexity
-
Quantum Büchi automata accept languages as limits of finite-word quantum languages
Measure Many Quantum Finite Automata on Infinite Words
-
SMT algorithm learns minimal weighted automata over semirings
SMT-Based Active Learning of Weighted Automata
-
Term rewriting cuts queries to learn tree automata
Learning Tree Automata with Term Rewriting
-
Brik recursion yields binary word with transcendental 1-density
Brik's sequence: a strange recursion
-
DFA primality decision is NP-hard
Deciding DFA-Primality is NP-Hard
-
MinMax RNCs recognize every regular language with constant gradients
MinMax Recurrent Neural Cascades
-
MinMax RNN cascades express all regular languages without vanishing gradients
MinMax Recurrent Neural Cascades
-
Temporal causal models encode linear bounded automata
Temporal Causal Models as a Model of Computation
-
Edit distance computable for finite-valued transducers
Edit Distance of Finite-Valued Transducers
-
Viability games gain decidability beyond pure counters
Infinite-state Games with Energy Objectives Beyond Counters
-
Viability games decidable on mixed pushdown-counter systems
Infinite-state Games with Energy Objectives Beyond Counters
-
Model finds resource-safe strategies for robots under mixed uncertainty
Resource-Constrained Robotic Planning in the face of Mixed Uncertainty
-
New language allows automatic verification of larger quantum programs
A Practical Specification Language for Automatic Quantum Program Verification (Technical Report)
-
Stack condition decides model checking for context-free hyperproperties
Logics for Context-free Hyperproperties
-
Hennie machines define linear size-to-height tree functions
Tree transducers of linear size-to-height increase (and the additive conjunction of linear logic)
-
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)