Research map / Learning theory and algorithms / Prediction and decision losses
Learning DFAs from Positive Examples Only via Word Counting
Benjamin Bordais, Daniel Neider
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| solve the word-counting task with an ILP encoding instead of the symbolic SAT-based algorithm | ILP algorithm (Gurobi) · 28 samples, n=4 and n=6 runtime | runtime | Hurt |
| start the symbolic algorithm from a DFA found by the word-counting heuristic (symbolic*) | symbolic algorithm · 10 hard samples (runtime >= 500s, n=8 except sample 08 n=7) | runtime | Mixed |
| run heuristic+symbolic* in a portfolio with the symbolic algorithm | symbolic algorithm · 10 hard samples (runtime >= 500s) | runtime | Improved |
| lower the starting score of the initial DFA given to the symbolic algorithm | symbolic* algorithm · samples with n=8 | runtime ratio | Mixed |
Closest papers by meaning
- Surprises in Proper Positive-Only Learning (NeurIPS 2026 · similarity 0.84)
- Generation from Noisy Examples (ICML 2025 · similarity 0.84)
- Subgoal-based Demonstration Learning for Formal Theorem Proving (ICML 2024 · similarity 0.83)
- Learning Juntas under Markov Random Fields (NeurIPS 2025 · similarity 0.83)
- Generalized Convergence Analysis of Tsetlin Automaton Based Algorithms: A Probabilistic Approach to Concept Learning (AAAI 2025 · similarity 0.83)
- On the Expressiveness and Length Generalization of Selective State Space Models on Regular Languages (AAAI 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
