archive
Every paper Pith has read. Search by title, abstract, or pith.
213 papers in cs.FL · page 1
-
Tool generates dependent event sequences using DFAs and transducers
AGDES: Automatic Generation of Dependent Event Sequences
-
Rado graph has the finite length property
The Finite Length Property of the Rado Graph and Friends
-
Tool verifies probabilistic logic in stochastic systems 10-1000x faster
SENTIL: A Runtime Verification Tool for Probabilistic Temporal Logic
-
Unique factorization systems yield combinatorial manifold categories
Combinatorial manifolds and Kleene's theorem, homotopically
-
NFA intersections built with O(mn) transitions
Intersecting Dense Automata
-
Complexity mapped for equilibria in multiplayer graph games
Equilibria in Multiplayer Graph Games: An Algorithmic Study
-
Compressed acceptor verifies control safety under deadline misses
Over-approximation of weakly-hard constraints for control systems verification (Extended)
-
Nonlinear bipermutive CA produce main-diagonal transversals at diameter 6
On the transversals of Latin squares generated by nonlinear bipermutive cellular automata
-
Linear structure drives CFLOBDD compression
Do CFLOBDDs Actually Make Use of Linear Structure?
-
Modular SCC decomposition speeds up Büchi complementation
Kofola 1.0: A Modular Approach to {\omega}-Regular Complementation and Inclusion Checking (Technical Report)
-
L# algorithm learns minimal separating DFA
An $L^{\#}$ Based Algorithm for Active Learning of Minimal Separating Automata
-
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
-
Flattening turns nested automata into ordinary ones for analysis
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
-
Five-letter pure morphic word avoids half-flips
Half-flips are 5-avoidable
-
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
-
Term rewriting deduces some queries in tree automaton learning
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 RNN cascades express all regular languages without vanishing gradients
MinMax Recurrent Neural Cascades
-
MinMax RNCs recognize every regular language with constant 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)