pith. sign in

arxiv: 2606.19822 · v1 · pith:OGQDLDK2new · submitted 2026-06-18 · 💻 cs.FL

Learning Alternating Real-Time Automata

Kazuki Kinoshita , Masaki Waga This is my paper

Pith reviewed 2026-06-26 15:26 UTC · model grok-4.3

classification 💻 cs.FL
keywords active learningalternating automatareal-time automatamembership queriesequivalence queriesautomata learningtimed systems
0
0 comments X

The pith

Alternating real-time automata accept the same languages as nondeterministic ones but with fewer states, and the AL*RTA algorithm learns them via membership and equivalence queries.

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

The paper defines alternating real-time automata and proves they match the languages accepted by nondeterministic real-time automata while using fewer states in many cases. It introduces the AL*RTA algorithm that learns such automata by combining alternation techniques with real-time handling, and proves the procedure always terminates. Experiments show the learned automata are typically smaller than those from the nondeterministic learner, although the alternating version asks more queries overall.

Core claim

Alternation improves succinctness of real-time automata without increasing their expressive power, and the AL*RTA procedure correctly learns any language accepted by an alternating real-time automaton from membership and equivalence queries.

What carries the argument

The AL*RTA algorithm, which adapts the state-construction and alternation-resolution steps from alternating finite automata learning to the timed constraints of real-time automata.

If this is right

  • Any language accepted by a nondeterministic real-time automaton is also accepted by some alternating real-time automaton of equal or smaller size.
  • The learning procedure returns a correct automaton after finitely many queries whenever the target is an alternating real-time automaton.
  • In practice the returned automata are smaller than those produced by the nondeterministic learner on the same examples.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Smaller automata could reduce the cost of later verification or monitoring tasks that operate on the learned model.
  • The extra queries required might be offset in domains where model size directly affects runtime performance.
  • Similar alternation-based learning could be attempted for other timed models whose nondeterministic versions already have learning algorithms.

Load-bearing premise

The target language must be exactly the set of words accepted by some alternating real-time automaton, and the learner receives unrestricted membership and equivalence answers.

What would settle it

A concrete language accepted by an alternating real-time automaton for which AL*RTA either fails to terminate or returns an automaton that does not accept the language.

Figures

Figures reproduced from arXiv: 2606.19822 by Kazuki Kinoshita, Masaki Waga.

Figure 1
Figure 1. Figure 1: An ARTA and its corresponding evidence AFA. The initial location for [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: An observation table for AL∗ and the corresponding AFA. The initial location formula of Ahyp is ℓ0. The black square represents a universal branching. Definition 4 (alternating finite automata). An alternating finite automa￾ton (AFA) is a 5-tuple A = (L, Σ, L0, F, δ), where L is a finite set of locations, Σ is a finite alphabet, L0 ∈ B+(L) is the initial location formula, F ⊆ L is the set of accepting loca… view at source ↗
Figure 3
Figure 3. Figure 3: Observation tables and ARTAs in the example in [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Observation table and the corresponding hypothesis in the sixth step. [PITH_FULL_IMAGE:figures/full_fig_p029_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Observation table and the corresponding hypothesis in the seventh step. [PITH_FULL_IMAGE:figures/full_fig_p030_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Observation table and the corresponding hypothesis in the eighth step. [PITH_FULL_IMAGE:figures/full_fig_p031_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Ninth observation table T9 [PITH_FULL_IMAGE:figures/full_fig_p033_7.png] view at source ↗
read the original abstract

We present the AL*RTA algorithm for learning alternating real-time automata (ARTAs) using membership and equivalence queries. AL*RTA combines ideas from AL*for learning alternating finite automata and NL*RTA for learning nondeterministic real-time automata. We first define ARTAs and show that alternation improves succinctness, although it does not increase expressive power. We then present AL*RTA and show its termination. Our empirical evaluation suggests that AL*RTA generally learns smaller automata than NL*RTA at the cost of more queries.

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 paper introduces alternating real-time automata (ARTAs) and presents the AL*RTA algorithm for actively learning them via membership and equivalence queries. It first defines ARTAs, proves that alternation yields strictly more succinct representations without increasing expressive power beyond nondeterministic real-time automata (NRTAs), establishes termination of AL*RTA by combining ideas from AL* and NL*RTA, and reports an empirical comparison in which AL*RTA produces smaller automata than NL*RTA at the expense of additional queries.

Significance. If the termination argument and empirical controls hold, the work extends query-based learning to alternating real-time models and supplies a concrete constructive procedure together with a direct head-to-head evaluation against NL*RTA. The succinctness result and the explicit termination claim are the primary technical contributions.

minor comments (3)
  1. [Abstract and Section 4] The abstract states that termination is shown, yet the main text should explicitly reference the section or lemma containing the termination argument so that readers can locate the proof without searching.
  2. [Empirical evaluation] The empirical section reports that AL*RTA learns smaller automata; the paper should state the precise benchmark suite, number of runs, and statistical controls (e.g., whether query counts are averaged over multiple random targets) to allow replication.
  3. [Preliminaries] Notation for the real-time constraints and the alternation operator should be introduced once with a small example before being used in the algorithm pseudocode.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the constructive summary and for recommending minor revision. No specific major comments were provided in the report, so we have no point-by-point responses to address. We will incorporate any minor suggestions during revision if they are communicated.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper introduces ARTAs by definition, combines known algorithms (AL* and NL*RTA) into AL*RTA, provides a termination argument for the new procedure, and reports an empirical comparison. No load-bearing step reduces a claimed result to a fitted parameter, self-definition, or self-citation chain; the termination proof and size/query trade-off are presented as independent constructive outcomes. This matches the default expectation for an algorithmic paper whose central claims remain self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard automata-theoretic definitions and the active learning query model; no new free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)
  • domain assumption Standard definitions of alternating automata, real-time automata, membership queries, and equivalence queries from prior literature.
    The algorithm is defined by reference to these established concepts.

pith-pipeline@v0.9.1-grok · 5599 in / 1083 out tokens · 26012 ms · 2026-06-26T15:26:33.430468+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

26 extracted references · 8 canonical work pages

  1. [1]

    GitHub: Leslieaj/NRTALearning.https://github.com/Leslieaj/NRTALearning, accessed: 2026-03-08

    2026

  2. [2]

    Alur, R., Dill, D.L.: A theory of timed automata. Theor. Comput. Sci.126(2), 183–235 (1994),https://doi.org/10.1016/0304-3975(94)90010-8

    work page doi:10.1016/0304-3975(94)90010-8 1994

  3. [3]

    In: TACAS (1)

    An, J., Chen, M., Zhan, B., Zhan, N., Zhang, M.: Learning one-clock timed au- tomata. In: TACAS (1). pp. 444–462. Lecture Notes in Computer Science, Springer (2020)

    2020

  4. [4]

    An, J., Wang, L., Zhan, B., Zhan, N., Zhang, M.: Learning real-time automata. Sci. China Inf. Sci.64(9) (2021)

    2021

  5. [5]

    ACM Trans

    An, J., Zhan, B., Zhan, N., Zhang, M.: Learning nondeterministic real-time au- tomata. ACM Trans. Embed. Comput. Syst.20(5s), 99:1–99:26 (2021)

    2021

  6. [6]

    Angluin, D.: Learning regular sets from queries and counterexamples. Inf. Comput. 75(2), 87–106 (1987),https://doi.org/10.1016/0890-5401(87)90052-6

    work page doi:10.1016/0890-5401(87)90052-6 1987

  7. [7]

    In: Yang, Q., Wooldridge, M.J

    Angluin, D., Eisenstat, S., Fisman, D.: Learning regular languages via alternating automata. In: Yang, Q., Wooldridge, M.J. (eds.) Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015. pp. 3308–3314. AAAI Press (2015),http://ijcai. org/Abstract/15/466

    2015

  8. [8]

    In: CAV (1)

    Argyros, G., D’Antoni, L.: The learnability of symbolic automata. In: CAV (1). pp. 427–445. Lecture Notes in Computer Science, Springer (2018)

    2018

  9. [9]

    Berndt, S., Liskiewicz, M., Lutter, M., Reischuk, R.: Learning resid- ual alternating automata. Inf. Comput.289(Part), 104981 (2022). https://doi.org/10.1016/J.IC.2022.104981

    work page doi:10.1016/j.ic.2022.104981 2022

  10. [10]

    In: Boutilier, C

    Bollig, B., Habermehl, P., Kern, C., Leucker, M.: Angluin-style learning of NFA. In: Boutilier, C. (ed.) IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11-17, 2009. pp. 1004–1009 (2009),http://ijcai.org/Proceedings/09/Papers/170.pdf

    2009

  11. [11]

    In: QEST+FORMATS

    Bruy` ere, V., Garhewal, B., P´ erez, G.A., Staquet, G., Vaandrager, F.W.: Active learning of mealy machines with timers. In: QEST+FORMATS. pp. 42–61. Lecture Notes in Computer Science, Springer (2025)

    2025

  12. [12]

    Chandra, A.K., Kozen, D., Stockmeyer, L.J.: Alternation. J. ACM28(1), 114–133 (1981). https://doi.org/10.1145/322234.322243

    work page doi:10.1145/322234.322243 1981

  13. [13]

    In: POPL

    D’Antoni, L., Veanes, M.: Minimization of symbolic automata. In: POPL. pp. 541–

  14. [14]

    Dima, C.: Real-time automata. J. Autom. Lang. Comb.6(1), 3–23 (2001)

    2001

  15. [15]

    In: TACAS (1)

    Drews, S., D’Antoni, L.: Learning symbolic automata. In: TACAS (1). pp. 173–189. Lecture Notes in Computer Science, Springer (2017)

    2017

  16. [16]

    Fisman, D., Frenkel, H., Zilles, S.: Inferring symbolic automata. Log. Methods Comput. Sci.19(2) (2023). https://doi.org/10.46298/lmcs-19(2:5)2023

    work page doi:10.46298/lmcs-19(2:5)2023 2023

  17. [17]

    Grinchtein, O., Jonsson, B., Leucker, M.: Learning of event-recording automata. Theor. Comput. Sci.411(47), 4029–4054 (2010)

    2010

  18. [18]

    In: ICFEM

    Kogel, P., Kl¨ os, V., Glesner, S.: Learning mealy machines with local timers. In: ICFEM. pp. 47–64. Lecture Notes in Computer Science, Springer (2023)

    2023

  19. [19]

    In: QEST+FORMATS

    Kogel, P., Schwabe, W., Glesner, S.: Mmlt/ik: Efficiently learning mealy machines with local timers by using imprecise symbol filters. In: QEST+FORMATS. pp. 143–159. Lecture Notes in Computer Science, Springer (2024)

    2024

  20. [20]

    Leiss, E.L.: Succinct representation of regular languages by boolean au- tomata. Theor. Comput. Sci.13, 323–330 (1981). https://doi.org/10.1016/S0304- 3975(81)80005-9 Learning Alternating Real-Time Automata 19

    work page doi:10.1016/s0304- 1981

  21. [21]

    Leiss, E.L.: Succinct representation of regular languages by boolean automata II. Theor. Comput. Sci.38, 133–136 (1985). https://doi.org/10.1016/0304- 3975(85)90215-4

    work page doi:10.1016/0304- 1985

  22. [22]

    Rivest, R.L., Schapire, R.E.: Inference of finite automata using homing sequences. Inf. Comput.103(2), 299–347 (1993). https://doi.org/10.1006/INCO.1993.1021

    work page doi:10.1006/inco.1993.1021 1993

  23. [23]

    Teng, Y., Chen, H., Mi, J., Zhang, M., An, J., Zhan, N.: Active learning of deter- ministic timed automata via timed classification tree. Sci. China Inf. Sci.68(12) (2025)

    2025

  24. [24]

    In: HSCC

    Teng, Y., Zhang, M., An, J.: Learning deterministic multi-clock timed automata. In: HSCC. pp. 6:1–6:11. ACM (2024)

    2024

  25. [25]

    In: CAV (1)

    Waga, M.: Active learning of deterministic timed automata with myhill-nerode style characterization. In: CAV (1). pp. 3–26. Lecture Notes in Computer Science, Springer (2023)

    2023

  26. [26]

    DRTA size

    Xu, R., An, J., Zhan, B.: Active learning of one-clock timed automata using constraint solving. In: ATVA. pp. 249–265. Lecture Notes in Computer Science, Springer (2022) A Omitted proofs A.1 Proof of Theorem 8 Theorem 8 (recalled).DRTAs and ARTAs have the same expressive power. Moreover, for any ARTA withnlocations, there is a DRTA rec- ognizing the same ...

    2022