pith. sign in

arxiv: 1906.11104 · v1 · pith:GWVPQDL7new · submitted 2019-06-26 · 💻 cs.FL

Approximate Learning of Limit-Average Automata

Jakub Michaliszyn , Jan Otop This is my paper

Pith reviewed 2026-05-25 15:04 UTC · model grok-4.3

classification 💻 cs.FL
keywords limit-average automataactive learningpassive learningPAC learnabilityNP-completenessweighted automataautomata learninguniform distribution
0
0 comments X

The pith

Limit-average automata can be learned almost-exactly in polynomial time via active queries.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies learning of limit-average automata, which evaluate infinite words by the limiting average of their weights. In the passive setting, these automata are not PAC-learnable because any sample providing sufficient information must be exponentially large with high probability, and the problem of finding an automaton consistent with a given sample is NP-complete. In the active setting, however, there exists a polynomial-time procedure that produces an automaton agreeing with the target on almost all words under the uniform distribution. Finding an automaton with fewer states that still approximates the target remains NP-complete. The main positive and negative results are shown specifically for the uniform distribution.

Core claim

Limit-average automata can be learned almost-exactly, i.e., we can learn in polynomial time an automaton that is consistent with the target automaton on almost all words.

What carries the argument

Active learning algorithm that outputs an automaton consistent with the target on almost all words under the uniform distribution.

Load-bearing premise

The positive learning result holds under the uniform distribution on words.

What would settle it

A family of limit-average automata for which every active learning algorithm requires superpolynomial time to output an automaton consistent on all but a vanishing fraction of words under the uniform distribution.

read the original abstract

Limit-average automata are weighted automata on infinite words that use average to aggregate the weights seen in infinite runs. We study approximate learning problems for limit-average automata in two settings: passive and active. In the passive learning case, we show that limit-average automata are not PAC-learnable as samples must be of exponential-size to provide (with good probability) enough details to learn an automaton. We also show that the problem of finding an automaton that fits a given sample is NP-complete. In the active learning case, we show that limit-average automata can be learned almost-exactly, i.e., we can learn in polynomial time an automaton that is consistent with the target automaton on almost all words. On the other hand, we show that the problem of learning an automaton that approximates the target automaton (with perhaps fewer states) is NP-complete. The abovementioned results are shown for the uniform distribution on words. We briefly discuss learning over different distributions.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript claims that limit-average automata (weighted automata on infinite words using limit-average aggregation) are not PAC-learnable in the passive setting under the uniform distribution, since exponential-size samples are required to ensure sufficient detail with high probability; additionally, finding an automaton consistent with a given sample is NP-complete. In the active setting, the paper establishes a polynomial-time algorithm for almost-exact learning, producing an automaton consistent with the target on a measure-1 set of infinite words; however, the problem of learning an approximating automaton (possibly with fewer states) is NP-complete. All stated results hold specifically for the uniform product measure on words, with other distributions discussed only briefly.

Significance. If the central claims and proofs hold, the work supplies precise complexity separations between passive and active learning for this class of quantitative automata, including a positive polynomial-time result for almost-exact active learning under the uniform measure. Explicit scoping of all theorems to the uniform distribution is a strength, as it permits clean statements without overclaiming generality. The NP-completeness results for sample fitting and approximation provide concrete hardness evidence. No machine-checked proofs or reproducible code are mentioned, but the complexity-theoretic framing allows direct comparison with related automata-learning results.

minor comments (3)
  1. [Abstract] Abstract: the phrase 'we briefly discuss learning over different distributions' is vague; a one-sentence indication of which distributions are considered and what changes (e.g., sampling probabilities or measure-1 sets) would improve clarity without lengthening the abstract.
  2. [Introduction / Preliminaries] The manuscript should include an explicit statement, early in the introduction or preliminaries, of the precise definition of the uniform product measure used for the almost-exact learning theorem (e.g., independent uniform letter probabilities).
  3. [Throughout] Notation for limit-average value and consistency on measure-1 sets should be introduced once and used uniformly; minor inconsistencies in symbol choice across sections would benefit from a consolidated notation table.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive evaluation of our manuscript and the recommendation for minor revision. The report accurately summarizes our main results on the separation between passive and active learning for limit-average automata under the uniform distribution. No specific major comments were raised.

Circularity Check

0 steps flagged

No circularity; standard complexity results on learnability.

full rationale

The paper states polynomial-time active learning for almost-exact consistency and NP-completeness results under the uniform distribution on words, with other distributions only briefly discussed. These are conventional complexity-theoretic claims (PAC-learnability, NP-completeness of fitting) with no reduction of any prediction or theorem to a fitted parameter, self-definition, or self-citation chain. The explicit scoping to uniform measure does not create a definitional loop or force the central claim by construction. The derivation chain is self-contained against external benchmarks such as standard automata learning theory.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review performed on abstract only; no free parameters, invented entities, or ad-hoc axioms are visible. The uniform distribution is treated as a domain assumption.

axioms (1)
  • standard math Standard complexity-theoretic assumptions (P ≠ NP) used to interpret NP-completeness statements
    Invoked implicitly when stating that fitting a sample is NP-complete.

pith-pipeline@v0.9.0 · 5683 in / 1131 out tokens · 27944 ms · 2026-05-25T15:04:44.146262+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages

  1. [1]

    Learning regular sets from queries and counterexamples

    Dana Angluin. Learning regular sets from queries and counterexamples. Information and computation , 75(2):87--106, 1987

    work page 1987

  2. [2]

    Learning a random DFA from uniform strings and state information

    Dana Angluin and Dongqu Chen. Learning a random DFA from uniform strings and state information. In ALT 2015 , pages 119--133, Cham, 2015. Springer International Publishing

    work page 2015

  3. [3]

    Learning regular omega languages

    Dana Angluin and Dana Fisman. Learning regular omega languages. Theor. Comput. Sci. , 650:57--72, 2016

    work page 2016

  4. [4]

    Principles of model checking

    Christel Baier and Joost - Pieter Katoen. Principles of model checking . MIT Press, 2008

    work page 2008

  5. [5]

    Learning weighted automata

    Borja Balle and Mehryar Mohri. Learning weighted automata. In CAI 2015 , pages 1--21, 2015

    work page 2015

  6. [6]

    On the rademacher complexity of weighted automata

    Borja Balle and Mehryar Mohri. On the rademacher complexity of weighted automata. In ALT 2015 , pages 179--193, 2015

    work page 2015

  7. [7]

    Generalization bounds for learning weighted automata

    Borja Balle and Mehryar Mohri. Generalization bounds for learning weighted automata. Theor. Comput. Sci. , 716:89--106, 2018

    work page 2018

  8. [8]

    A canonical form for weighted automata and applications to approximate minimization

    Borja Balle, Prakash Panangaden, and Doina Precup. A canonical form for weighted automata and applications to approximate minimization. In LICS 2015 , pages 701--712, 2015

    work page 2015

  9. [9]

    Learning functions represented as multiplicity automata

    Amos Beimel, Francesco Bergadano, Nader Bshouty, Eyal Kushilevitz, and Stefano Varricchio. Learning functions represented as multiplicity automata. Journal of the ACM , 47, 10 1999

    work page 1999

  10. [10]

    Regular repair of specifications

    Michael Benedikt, Gabriele Puppis, and Cristian Riveros. Regular repair of specifications. In LICS 2011 , pages 335--344, 2011

    work page 2011

  11. [11]

    Henzinger, and Orna Kupferman

    Udi Boker, Krishnendu Chatterjee, Thomas A. Henzinger, and Orna Kupferman. Temporal specifications with accumulative values. ACM Trans. Comput. Log. , 15(4):27:1--27:25, 2014

    work page 2014

  12. [12]

    Angluin-style learning of NFA

    Benedikt Bollig, Peter Habermehl, Carsten Kern, and Martin Leucker. Angluin-style learning of NFA . In IJCAI 2009 , pages 1004--1009, 2009

    work page 2009

  13. [13]

    Averaging in LTL

    Patricia Bouyer, Nicolas Markey, and Raj Mohan Matteplackel. Averaging in LTL . In CONCUR 2014 , pages 266--280, 2014

    work page 2014

  14. [14]

    Henzinger, and Arjun Radhakrishna

    Pavol Cern \' y , Thomas A. Henzinger, and Arjun Radhakrishna. Quantitative abstraction refinement. In POPL 2013 , pages 115--128, 2013

    work page 2013

  15. [15]

    Henzinger

    Krishnendu Chatterjee, Laurent Doyen, and Thomas A. Henzinger. Quantitative languages. ACM TOCL , 11(4):23, 2010

    work page 2010

  16. [16]

    Henzinger, and Jan Otop

    Krishnendu Chatterjee, Thomas A. Henzinger, and Jan Otop. Quantitative automata under probabilistic semantics. In LICS 2016 , pages 76--85, 2016

    work page 2016

  17. [17]

    Grammatical Inference: Learning Automata and Grammars

    Colin de la Higuera. Grammatical Inference: Learning Automata and Grammars . Cambridge University Press, New York, NY, USA, 2010

    work page 2010

  18. [18]

    Handbook of Weighted Automata

    Manfred Droste, Werner Kuich, and Heiko Vogler. Handbook of Weighted Automata . Springer, 1st edition, 2009

    work page 2009

  19. [19]

    W. Feller. An introduction to probability theory and its applications . Wiley, 1971

    work page 1971

  20. [20]

    Inferring regular languages and \( \) -languages

    Dana Fisman. Inferring regular languages and \( \) -languages. J. Log. Algebr. Meth. Program. , 98:27--49, 2018

    work page 2018

  21. [21]

    Complexity of automaton identification from given data

    E Mark Gold. Complexity of automaton identification from given data. Information and control , 37(3):302--320, 1978

    work page 1978

  22. [22]

    Learning multiplicity tree automata

    Amaury Habrard and Jos \' e Oncina. Learning multiplicity tree automata. In ICGI 2006 , pages 268--280, 2006

    work page 2006

  23. [23]

    Henzinger and Jan Otop

    Thomas A. Henzinger and Jan Otop. Model measuring for discrete and hybrid systems. Nonlinear Analysis: Hybrid Systems , 23:166 -- 190, 2017

    work page 2017

  24. [24]

    An efficient membership-query algorithm for learning dnf with respect to the uniform distribution

    Jeffrey C Jackson. An efficient membership-query algorithm for learning dnf with respect to the uniform distribution. Journal of Computer and System Sciences , 55(3):414--440, 1997

    work page 1997

  25. [25]

    Cryptographic limitations on learning boolean formulae and finite automata

    Michael Kearns and Leslie Valiant. Cryptographic limitations on learning boolean formulae and finite automata. Journal of the ACM (JACM) , 41(1):67--95, 1994

    work page 1994

  26. [26]

    An introduction to computational learning theory

    Michael J Kearns, Umesh Virkumar Vazirani, and Umesh Vazirani. An introduction to computational learning theory . MIT Press, 1994

    work page 1994

  27. [27]

    Kevin J. Lang. Random DFA's can be approximately learned from sparse uniform examples. In COLT 1992 , pages 45--52, 1992

    work page 1992

  28. [28]

    Complexity of equivalence and learning for multiplicity tree automata

    Ines Marusic and James Worrell. Complexity of equivalence and learning for multiplicity tree automata. Journal of Machine Learning Research , 16:2465--2500, 2015

    work page 2015

  29. [29]

    Non-deterministic weighted automata on random words

    Jakub Michaliszyn and Jan Otop. Non-deterministic weighted automata on random words. In CONCUR 2018 , volume 118 of LIPIcs , pages 10:1--10:16, 2018

    work page 2018

  30. [30]

    The discrete basis problem

    Pauli Miettinen, Taneli Mielik \"a inen, Aristides Gionis, Gautam Das, and Heikki Mannila. The discrete basis problem. In European Conference on Principles of Data Mining and Knowledge Discovery , pages 335--346. Springer, 2006

    work page 2006

  31. [31]

    Learning nominal automata

    Joshua Moerman, Matteo Sammartino, Alexandra Silva, Bartek Klin, and Michal Szynwelski. Learning nominal automata. In POPL 2017 , pages 613--625, 2017

    work page 2017

  32. [32]

    Inferring regular languages in polynomial updated time

    Jos \'e Oncina and Pedro Garcia. Inferring regular languages in polynomial updated time. In Pattern recognition and image analysis: selected papers from the IVth Spanish Symposium , pages 49--61. World Scientific, 1992

    work page 1992

  33. [33]

    Inductive inference, DFAs , and computational complexity

    Leonard Pitt. Inductive inference, DFAs , and computational complexity. In International Workshop on Analogical and Inductive Inference , pages 18--44. Springer, 1989

    work page 1989

  34. [34]

    The minimum consistent DFA problem cannot be approximated within any polynomial

    Leonard Pitt and Manfred K Warmuth. The minimum consistent DFA problem cannot be approximated within any polynomial. Journal of the ACM (JACM) , 40(1):95--142, 1993

    work page 1993

  35. [35]

    A theory of the learnable

    Leslie G Valiant. A theory of the learnable. In Proceedings of the sixteenth annual ACM symposium on Theory of computing , pages 436--445. ACM, 1984

    work page 1984