Image de couverture de livre

Learning DFAs from Positive Examples Only via Word Counting

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Bordais, Benjamin, Neider, Daniel
Format:	Preprint
Publié:	2025
Sujets:	Computational Complexity
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

A framework for computing upper bounds in passive learning settings
par: Bordais, Benjamin, et autres
Publié: (2025)

Learning Branching-Time Properties in CTL and ATL via Constraint Solving
par: Bordais, Benjamin, et autres
Publié: (2024)

The Complexity of Learning Temporal Properties
par: Bordais, Benjamin, et autres
Publié: (2024)

Learning Tree Pattern Transformations
par: Neider, Daniel, et autres
Publié: (2024)

Counting Small Induced Subgraphs: Hardness via Fourier Analysis
par: Curticapean, Radu, et autres
Publié: (2024)

The Counting General Dominating Set Framework
par: Zheng, Jiayi, et autres
Publié: (2026)

The Complexity of Logarithmic Space Bounded Counting Classes
par: Vijayaraghavan, T. C.
Publié: (2025)

Low Sets and Closure Properties of Counting Function Classes
par: Ivanashev, Yaroslav
Publié: (2025)

Lower Bounds for Subset Sum in Resolution with Modular Counting
par: Part, Fedor
Publié: (2022)

Hilbert's Nullstellensatz is in the Counting Hierarchy
par: Andrews, Robert, et autres
Publié: (2026)

Counting Triangulations of Fixed Cardinal Degrees
par: Chambers, Erin, et autres
Publié: (2025)

From Alternation to FPRAS: Toward a Complexity Classification of Approximate Counting
par: Hecher, Markus, et autres
Publié: (2025)

The Complexity of Counting Turns in the Line-Based Dial-a-Ride Problem
par: Lauerbach, Antonio, et autres
Publié: (2024)

Algorithmic Structure in Subset Sum: Deterministic In-Bound Navigation and the Counting Complexity Divide
par: Nkosi, Thami
Publié: (2025)

Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial
par: Curticapean, Radu, et autres
Publié: (2025)

Modular Counting CSP: Reductions and Algorithms
par: Kazeminia, Amirhossein, et autres
Publié: (2025)

Computing the Elementary Symmetric Polynomials in Positive Characteristics
par: Orzel, Ian
Publié: (2025)

Counting Subgraphs in Somewhere Dense Graphs
par: Bressan, Marco, et autres
Publié: (2022)

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
par: Döring, Simon, et autres
Publié: (2024)

Model Counting for Dependency Quantified Boolean Formulas
par: Fung, Long-Hin, et autres
Publié: (2025)

Finite Variable Counting Logics with Restricted Requantification
par: Raßmann, Simon, et autres
Publié: (2024)

Review of Automaton Learning Algorithms with Polynomial Complexity -- Completely Solved Examples
par: Haneef, Farah
Publié: (2024)

Complexity of the Guarded Two-Variable Fragment with Counting Quantifiers
par: Pratt-Hartmann, Ian
Publié: (2006)

Positive Univariate Polynomials: SOS certificates, algorithms, bit complexity, and T-systems
par: Bender, Matías, et autres
Publié: (2025)

Frontier Space-Time Algorithms Using Only Full Memory
par: Chmel, Petr, et autres
Publié: (2026)

The Complexity of Finding and Counting Subtournaments
par: Döring, Simon, et autres
Publié: (2025)

Work-Efficient Parallel Counting via Sampling
par: Liu, Hongyang, et autres
Publié: (2024)

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
par: Focke, Jacob, et autres
Publié: (2022)

The Complexity of Counting Small Sub-Hypergraphs
par: Bressan, Marco, et autres
Publié: (2025)

Multiquadratic Sum-of-Squares Lower Bounds Imply VNC$^1$ $\neq$ VNP
par: Rossman, Benjamin, et autres
Publié: (2025)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
par: Wang, Yichuan
Publié: (2024)

Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations
par: Focke, Jacob, et autres
Publié: (2021)

Compilation and Fast Model Counting beyond CNF
par: de Colnet, Alexis, et autres
Publié: (2025)

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
par: Grossman, Ofer, et autres
Publié: (2023)

Symmetric Distributions from Shallow Circuits
par: Kane, Daniel M., et autres
Publié: (2025)

Epistemic Logic Programs: Non-Ground and Counting Complexity
par: Eiter, Thomas, et autres
Publié: (2025)

P vs. NP
par: Uribe, Daniel
Publié: (2016)

Between the deterministic and non-deterministic query complexity
par: Gerbner, Dániel
Publié: (2019)

Hard-to-Sample Distributions from Robust Extractors
par: Byramji, Farzan, et autres
Publié: (2026)

The Computational Complexity of Counting Linear Regions in ReLU Neural Networks
par: Stargalla, Moritz, et autres
Publié: (2025)