On Minimization and Learning of Deterministic $\omega$-Automata in the Presence of Don't Care Words

Christof L\"oding; Max Philip Stachon

arxiv: 2211.08787 · v6 · submitted 2022-11-16 · 💻 cs.FL

On Minimization and Learning of Deterministic ω-Automata in the Presence of Don't Care Words

Christof L\"oding , Max Philip Stachon This is my paper

Pith reviewed 2026-05-24 11:27 UTC · model grok-4.3

classification 💻 cs.FL

keywords deterministic omega-automataparity automatadon't care wordsminimizationright-congruenceweak deterministic Büchi automataactive learningNP-hardness

0 comments

The pith

The number of priorities in deterministic parity automata can be minimized efficiently under arbitrary don't care words.

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

The paper establishes that the number of priorities required by a deterministic parity automaton can be reduced to the minimum in polynomial time when an arbitrary set of words is designated as don't cares. This follows from a general minimization procedure that also produces an efficient algorithm for the case of deterministic parity automata with informative right-congruence in the absence of don't cares. For don't care sets whose right-congruence is trivial, weak deterministic Büchi automata possess a unique minimal representative that is characterized by a congruence relation and can be constructed efficiently. The same trivial right-congruence condition does not preserve uniqueness for automata with informative right-congruence, and minimization in that setting is NP-hard. The authors further extend an existing active learning procedure for weak deterministic Büchi automata to accept an additional don't care set with trivial right-congruence.

Core claim

The number of priorities in a deterministic parity automaton can be minimized in polynomial time under an arbitrary don't care set. This is obtained from a general minimization procedure applicable to deterministic parity automata that possess an informative right-congruence. For the subclass of weak deterministic Büchi automata and don't care languages whose right-congruence is trivial, the minimal automaton is unique and can be computed efficiently; it is characterized by the congruence that merges states indistinguishable under the don't care condition. In contrast, when the automata have informative right-congruence, even with trivial don't care congruence, there is no unique minimal wDB

What carries the argument

The general minimization procedure for deterministic parity automata under don't care conditions that reduces the priority count while preserving acceptance behavior.

If this is right

An efficient algorithm exists to minimize priorities in any deterministic parity automaton given any don't care set.
The same general result yields an efficient minimization for deterministic parity automata with informative right-congruence without don't cares.
Weak deterministic Büchi automata admit a unique minimal form under don't care sets with trivial right-congruence, characterized by a specific congruence.
Minimization of deterministic automata with informative right-congruence under trivial right-congruence don't cares is NP-hard.
The active learning algorithm for weak deterministic Büchi automata can be extended to handle don't care words with trivial right-congruence.

Where Pith is reading between the lines

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

The separation between trivial and informative right-congruences may guide the design of don't care handling in other classes of omega-automata.
One could investigate whether similar priority minimization techniques apply to nondeterministic parity automata or other acceptance conditions.
Practical implementations of the learning extension might improve specification mining when some behaviors are unspecified.

Load-bearing premise

The results on uniqueness and efficient computation for weak deterministic Büchi automata hold only when the don't care words induce the trivial right-congruence.

What would settle it

A deterministic parity automaton together with a don't care set for which no polynomial-time procedure produces an equivalent automaton with the fewest priorities.

Figures

Figures reproduced from arXiv: 2211.08787 by Christof L\"oding, Max Philip Stachon.

**Figure 1.** Figure 1: Illustration of DON’T CARE PRIORITY OPTIMIZATION. An optimal parity condition consistent with (F ′ 0 , F ′ 1 ) can redefine the priority of q0 to 2 and thus use one priority less. there is no deterministic ω-automaton B of the same type with L(A) ≡D L(B) with less states than A. 3. Priority optimization In this section we consider the problem of optimizing a parity condition under a given don’t care set, r… view at source ↗

**Figure 2.** Figure 2: The DBA A has 3 different corresponding D-minimal DBA for the set of don’t care words D := Σ ∗ b ω. Proof: Consider the DBA A in [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗

**Figure 3.** Figure 3: The D′ -minimal DPA Acol and the DPA AG for G = ({v1, v2, v3}, {(v1, v2),(v1, v3)}) recognize D′ -equivalent ω-languages. The don’t care set then includes all words α in which labels of the form xv occur infinitely often, or from some point on successive vertices vv′ in α are not connected by an edge. With this don’t care set, a D-minimal DPA Acol can use one state for each color class in a k-coloring inst… view at source ↗

**Figure 4.** Figure 4: The situation described in Lemma 5.3 with [PITH_FULL_IMAGE:figures/full_fig_p015_4.png] view at source ↗

read the original abstract

We study minimization problems for deterministic $\omega$-automata in the presence of don't care words. We prove that the number of priorities in deterministic parity automata can be efficiently minimized under an arbitrary set of don't care words. We derive that from a more general result from which one also obtains an efficient minimization algorithm for deterministic parity automata with informative right-congruence (without don't care words). We then analyze languages of don't care words with a trivial right-congruence. For such sets of don't care words it is known that weak deterministic B\"uchi automata (WDBA) have a unique minimal automaton that can be efficiently computed from a given WDBA (Eisinger, Klaedtke 2006). We give a congruence-based characterization of the corresponding minimal WDBA, and show that the don't care minimization results for WDBA do not extend to deterministic $\omega$-automata with informative right-congruence: for this class there is no unique minimal automaton for a given don't care set with trivial right congruence, and the minimization problem is NP-hard. Finally, we extend an active learning algorithm for WDBA (Maler, Pnueli 1995) to the setting with an additional set of don't care words with trivial right-congruence.

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.

Desk Editor's Note private letter to a colleague

The paper gives an efficient minimization for the number of priorities in deterministic parity automata under arbitrary don't cares, derived from a general result that also covers the informative right-congruence case without don't cares.

read the letter

The main thing to know is that this paper shows how to efficiently minimize the number of priorities in deterministic parity automata when there is an arbitrary set of don't care words, and they get this from a general result that also gives minimization for the informative right-congruence case without don't cares. They do a good job laying out the positive results first and then showing the limitations for weak deterministic Büchi automata when the right-congruence is informative. The characterization using congruences for the minimal WDBA under trivial right-congruence on don't cares is clear and directly extends the 2006 work by Eisinger and Klaedtke. The NP-hardness for minimization in the informative case is a useful boundary result, and extending the Maler-Pnueli learning algorithm to include don't cares with trivial congruence makes sense as an application. The soft spots are minor. The abstract states the results cleanly, but without seeing the full algorithm or the proof of the general result, it's hard to judge if the efficiency holds in practice or if there are edge cases with the don't care sets. The uniqueness failure and hardness are shown, but the paper notes that the positive uniqueness holds only for trivial right-congruence, which they demonstrate is necessary. No major gaps in the logic from what's described. This is targeted at researchers in automata theory and formal methods who care about minimization and learning of omega-automata. Someone working on tools for verification might find the minimization useful for reducing state spaces. It is worth sending to peer review as the results are concrete and the distinctions between automaton classes are well-motivated.

Referee Report

0 major / 2 minor

Summary. The paper claims to prove that the number of priorities in deterministic parity automata can be efficiently minimized under an arbitrary set of don't care words. This follows from a more general result that also yields an efficient minimization algorithm for deterministic parity automata with informative right-congruence (without don't cares). For don't care words with trivial right-congruence, it gives a congruence-based characterization of the minimal weak deterministic Büchi automaton (extending Eisinger-Klaedtke 2006) and shows that uniqueness and efficient computability fail for the informative right-congruence case, where minimization is NP-hard. It also extends the Maler-Pnueli active learning algorithm for WDBA to the don't-care setting with trivial right-congruence.

Significance. If the results hold, they advance automata theory by supplying efficient priority-minimization procedures for parity automata under don't cares—an important class for verification and synthesis—and by cleanly delineating the boundary between the tractable (trivial right-congruence) and intractable (informative right-congruence) cases for WDBA. The derivation of multiple positive results from a single general theorem is a strength, as is the explicit extension of the 1995 learning algorithm. These contributions are directly usable in tools that manipulate ω-automata.

minor comments (2)

[Abstract] Abstract: the statement that minimization is 'efficient' would be strengthened by naming the complexity class (e.g., polynomial time) rather than leaving it implicit.
The manuscript states proofs and complexity results clearly in the abstract, but the absence of explicit algorithm pseudocode or a high-level complexity analysis in the provided summary text makes independent verification of the claimed polynomial-time bounds more difficult.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive evaluation and the recommendation of minor revision. The provided summary accurately captures the paper's contributions on priority minimization for deterministic parity automata under don't care words, the general result, the congruence characterization for trivial right-congruence WDBA, the NP-hardness result for informative right-congruence, and the extension of the Maler-Pnueli learning algorithm.

Circularity Check

0 steps flagged

No significant circularity; derivation relies on external citations and standard automata properties

full rationale

The paper's central positive claims (efficient minimization of priorities in DPA under don't cares, and for informative right-congruence) are stated as proven results derived from a general theorem, without reducing to self-definitions or fitted inputs. The WDBA uniqueness result is explicitly attributed to the external Eisinger-Klaedtke 2006 paper (different authors), and the learning extension builds on Maler-Pnueli 1995. Negative results (non-uniqueness and NP-hardness for informative right-congruence) are established via explicit counterexamples and hardness arguments. No load-bearing self-citation chains, ansatzes smuggled via citation, or renamings of known results appear in the provided abstract and claims. The derivation chain is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard automata-theoretic concepts such as right-congruences and parity acceptance conditions. No free parameters are fitted to data. No new entities are postulated.

axioms (2)

standard math Right-congruence relations on words induce equivalence classes that determine automaton states and minimality
Invoked throughout for characterizations of minimal automata and for distinguishing trivial vs. informative cases.
standard math Deterministic omega-automata acceptance is defined via parity or Büchi conditions on infinite runs
Background assumption used to define the automata classes under study.

pith-pipeline@v0.9.0 · 5765 in / 1528 out tokens · 38269 ms · 2026-05-24T11:27:15.972889+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

[1]

Introduction to Automata Theory, Languages, and Computation

Hopcroft JE, Ullman JD. Introduction to Automata Theory, Languages, and Computation. Addison Wesley, 1979

work page 1979
[2]

Learning regular sets from queries and counterexamples

Angluin D. Learning regular sets from queries and counterexamples. Information and Computa- tion, 1987. 75(2):87 – 106. doi:https://doi.org/10.1016/0890-5401(87)90052-6. URL http://www. sciencedirect.com/science/article/pii/0890540187900526

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

State Reduction in Incompletely Specified Finite-State Machines

Pfleeger CP. State Reduction in Incompletely Specified Finite-State Machines. IEEE Transactions on Computers, 1973. C-22(12):87–106. C. L ¨oding and M.P . Stachon/ Minimization and Learning of ω-Automata with Don’t Cares 87

work page 1973
[4]

Beyond Hyper-Minimisation—Minimising DBAs and DPAs is NP-Complete

Schewe S. Beyond Hyper-Minimisation—Minimising DBAs and DPAs is NP-Complete. In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2010

work page 2010
[5]

Deterministic w Automata vis-a-vis Deterministic Buchi Automata

Krishnan SC, Puri A, Brayton RK. Deterministic w Automata vis-a-vis Deterministic Buchi Automata. In: Algorithms and Computation, 5th International Symposium, ISAAC ’94, Beijing, P. R. China, August 25-27, 1994, Proceedings, volume 834 ofLecture Notes in Computer Science. Springer, 1994 pp. 378–386. doi:10.1007/3-540-58325-4 \ 202. URL https://doi.org/10....

work page doi:10.1007/3-540-58325-4 1994
[6]

Automata on Infinite Objects

Thomas W. Automata on Infinite Objects. In: Leeuwen JV (ed.), Formal Models and Semantics, Handbook of Theoretical Computer Science, pp. 133–191. Elsevier, Amsterdam. ISBN 978-0-444-88074-1, 1990. doi:https://doi.org/10.1016/B978-0-444-88074-1.50009-3. URL https://www.sciencedirect.com/ science/article/pii/B9780444880741500093

work page doi:10.1016/b978-0-444-88074-1.50009-3 1990
[7]

Automata, Logics, and Infinite Games: A Guide to Current Research [outcome of a Dagstuhl seminar, February 2001], volume 2500 of Lecture Notes in Computer Science

Gr ¨adel E, Thomas W, Wilke T (eds.). Automata, Logics, and Infinite Games: A Guide to Current Research [outcome of a Dagstuhl seminar, February 2001], volume 2500 of Lecture Notes in Computer Science . Springer, 2002. ISBN 3-540-00388-6. doi:10.1007/3-540-36387-4. URL https://doi.org/10.1007/ 3-540-36387-4

work page doi:10.1007/3-540-36387-4 2001
[8]

Efficient minimization of deterministic weak ω-automata

L ¨oding C. Efficient minimization of deterministic weak ω-automata. Information Processing Let- ters, 2001. 79(3):105 – 109. doi:https://doi.org/10.1016/S0020-0190(00)00183-6. URL http://www. sciencedirect.com/science/article/pii/S0020019000001836

work page doi:10.1016/s0020-0190(00)00183-6 2001
[9]

Automatentheoretische und Automatenfreie Charakterisierung Toplogischer Klassen Regul¨arer Folgenmengen

L Staiger KW. Automatentheoretische und Automatenfreie Charakterisierung Toplogischer Klassen Regul¨arer Folgenmengen. Elektron. Informationsverarbeitung und Kybernetik EIK 10 , 1974. p. 379 – 392

work page 1974
[10]

On syntactic congruences for omega-languages

Maler O, Staiger L. On syntactic congruences for omega-languages. Theoretical Computer Science, 1997. 183(1):93–112. doi:https://doi.org/10.1016/S0304-3975(96)00312-X. Formal Language Theory, URL https://www.sciencedirect.com/science/article/pii/S030439759600312X

work page doi:10.1016/s0304-3975(96)00312-x 1997
[11]

On omega-regular sets

Wagner K. On omega-regular sets. Information and Control , 1979. 43(2):123–177. doi:https://doi. org/10.1016/S0019-9958(79)90653-3. URL https://www.sciencedirect.com/science/article/ pii/S0019995879906533

work page doi:10.1016/s0019-9958(79)90653-3 1979
[12]

On the Learnability of Infinitary Regular Sets

Maler O, Pnueli A. On the Learnability of Infinitary Regular Sets. Information and Computation , 1995. 118(2):316 – 326. doi:https://doi.org/10.1006/inco.1995.1070. URL http://www.sciencedirect. com/science/article/pii/S089054018571070X

work page doi:10.1006/inco.1995.1070 1995
[13]

Learning regular omega languages

Angluin D, Fisman D. Learning regular omega languages. Theor . Comput. Sci., 2016. 650:57–72. doi: 10.1016/j.tcs.2016.07.031. URL https://doi.org/10.1016/j.tcs.2016.07.031

work page doi:10.1016/j.tcs.2016.07.031 2016
[14]

Don’t Care Words with an Application to the Automata-Based Approach for Real Addition

Eisinger J, Klaedtke F. Don’t Care Words with an Application to the Automata-Based Approach for Real Addition. In: Computer Aided Verification, 18th International Conference, CA V 2006, volume 4144 of Lecture Notes in Computer Science . Springer. ISBN 3-540-37406-X, 2006 pp. 67–80. doi: 10.1007/11817963. URL https://doi.org/10.1007/11817963

work page doi:10.1007/11817963 2006
[15]

Regular omega-Languages with an Informative Right Congruence

Angluin D, Fisman D. Regular omega-Languages with an Informative Right Congruence. Electronic Proceedings in Theoretical Computer Science , 2018. 277:265–279. doi:10.4204/eptcs.277.19. URL http://dx.doi.org/10.4204/EPTCS.277.19

work page doi:10.4204/eptcs.277.19 2018
[16]

Computing the Rabin Index of a Parity Automaton

Carton O, Maceiras R. Computing the Rabin Index of a Parity Automaton. RAIRO Theoretical Informatics and Applications, 1999. 33(6):495–506. 88 C. L ¨oding and M.P . Stachon/ Minimization and Learning of ω-Automata with Don’t Cares

work page 1999
[17]

New Optimizations and Heuristics for Determinization of B ¨uchi Automata

L ¨oding C, Pirogov A. New Optimizations and Heuristics for Determinization of B ¨uchi Automata. In: Proceedings of the 17th International Symposium on Automated Technology for Verification and Analysis (ATV A’19), volume 11781 ofLecture Notes in Computer Science . Springer, 2019

work page 2019
[18]

Constructing Deterministic ω-Automata from Examples by an Extension of the RPNI Algorithm

Bohn L, L ¨oding C. Constructing Deterministic ω-Automata from Examples by an Extension of the RPNI Algorithm. In: 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, volume 202 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f ¨ur Informatik, 2021 pp. 20:1–20:18. doi:10.4230/LIPIcs.MFCS.2021.20. URL https://doi.org/10.4...

work page doi:10.4230/lipics.mfcs.2021.20 2021
[19]

Polynomial Identification of omega-Automata

Angluin D, Fisman D, Shoval Y . Polynomial Identification of omega-Automata. CoRR, 2022. abs/2209.09336. doi:10.48550/arXiv.2209.09336. 2209.09336, URL https://doi.org/10.48550/ arXiv.2209.09336

work page doi:10.48550/arxiv.2209.09336 2022
[20]

Reducibility among Combinatorial Problems, pp

Karp RM. Reducibility among Combinatorial Problems, pp. 85–103. Springer US, Boston, MA. ISBN 978-1-4684-2001-2, 1972

work page 2001
[21]

Meyer PJ, Sickert S, Luttenberger M. Strix: Explicit Reactive Synthesis Strikes Back! In: Computer Aided Verification - 30th International Conference, CA V 2018, Held as Part of the Federated Logic Conference, FloC 2018, Oxford, UK, July 14-17, 2018, Proceedings, Part I. 2018 pp. 578–586. doi: 10.1007/978-3-319-96145-3 \ 31. URL https://doi.org/10.1007/97...

work page doi:10.1007/978-3-319-96145-3 2018

[1] [1]

Introduction to Automata Theory, Languages, and Computation

Hopcroft JE, Ullman JD. Introduction to Automata Theory, Languages, and Computation. Addison Wesley, 1979

work page 1979

[2] [2]

Learning regular sets from queries and counterexamples

Angluin D. Learning regular sets from queries and counterexamples. Information and Computa- tion, 1987. 75(2):87 – 106. doi:https://doi.org/10.1016/0890-5401(87)90052-6. URL http://www. sciencedirect.com/science/article/pii/0890540187900526

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

[3] [3]

State Reduction in Incompletely Specified Finite-State Machines

Pfleeger CP. State Reduction in Incompletely Specified Finite-State Machines. IEEE Transactions on Computers, 1973. C-22(12):87–106. C. L ¨oding and M.P . Stachon/ Minimization and Learning of ω-Automata with Don’t Cares 87

work page 1973

[4] [4]

Beyond Hyper-Minimisation—Minimising DBAs and DPAs is NP-Complete

Schewe S. Beyond Hyper-Minimisation—Minimising DBAs and DPAs is NP-Complete. In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2010

work page 2010

[5] [5]

Deterministic w Automata vis-a-vis Deterministic Buchi Automata

Krishnan SC, Puri A, Brayton RK. Deterministic w Automata vis-a-vis Deterministic Buchi Automata. In: Algorithms and Computation, 5th International Symposium, ISAAC ’94, Beijing, P. R. China, August 25-27, 1994, Proceedings, volume 834 ofLecture Notes in Computer Science. Springer, 1994 pp. 378–386. doi:10.1007/3-540-58325-4 \ 202. URL https://doi.org/10....

work page doi:10.1007/3-540-58325-4 1994

[6] [6]

Automata on Infinite Objects

Thomas W. Automata on Infinite Objects. In: Leeuwen JV (ed.), Formal Models and Semantics, Handbook of Theoretical Computer Science, pp. 133–191. Elsevier, Amsterdam. ISBN 978-0-444-88074-1, 1990. doi:https://doi.org/10.1016/B978-0-444-88074-1.50009-3. URL https://www.sciencedirect.com/ science/article/pii/B9780444880741500093

work page doi:10.1016/b978-0-444-88074-1.50009-3 1990

[7] [7]

Automata, Logics, and Infinite Games: A Guide to Current Research [outcome of a Dagstuhl seminar, February 2001], volume 2500 of Lecture Notes in Computer Science

Gr ¨adel E, Thomas W, Wilke T (eds.). Automata, Logics, and Infinite Games: A Guide to Current Research [outcome of a Dagstuhl seminar, February 2001], volume 2500 of Lecture Notes in Computer Science . Springer, 2002. ISBN 3-540-00388-6. doi:10.1007/3-540-36387-4. URL https://doi.org/10.1007/ 3-540-36387-4

work page doi:10.1007/3-540-36387-4 2001

[8] [8]

Efficient minimization of deterministic weak ω-automata

L ¨oding C. Efficient minimization of deterministic weak ω-automata. Information Processing Let- ters, 2001. 79(3):105 – 109. doi:https://doi.org/10.1016/S0020-0190(00)00183-6. URL http://www. sciencedirect.com/science/article/pii/S0020019000001836

work page doi:10.1016/s0020-0190(00)00183-6 2001

[9] [9]

Automatentheoretische und Automatenfreie Charakterisierung Toplogischer Klassen Regul¨arer Folgenmengen

L Staiger KW. Automatentheoretische und Automatenfreie Charakterisierung Toplogischer Klassen Regul¨arer Folgenmengen. Elektron. Informationsverarbeitung und Kybernetik EIK 10 , 1974. p. 379 – 392

work page 1974

[10] [10]

On syntactic congruences for omega-languages

Maler O, Staiger L. On syntactic congruences for omega-languages. Theoretical Computer Science, 1997. 183(1):93–112. doi:https://doi.org/10.1016/S0304-3975(96)00312-X. Formal Language Theory, URL https://www.sciencedirect.com/science/article/pii/S030439759600312X

work page doi:10.1016/s0304-3975(96)00312-x 1997

[11] [11]

On omega-regular sets

Wagner K. On omega-regular sets. Information and Control , 1979. 43(2):123–177. doi:https://doi. org/10.1016/S0019-9958(79)90653-3. URL https://www.sciencedirect.com/science/article/ pii/S0019995879906533

work page doi:10.1016/s0019-9958(79)90653-3 1979

[12] [12]

On the Learnability of Infinitary Regular Sets

Maler O, Pnueli A. On the Learnability of Infinitary Regular Sets. Information and Computation , 1995. 118(2):316 – 326. doi:https://doi.org/10.1006/inco.1995.1070. URL http://www.sciencedirect. com/science/article/pii/S089054018571070X

work page doi:10.1006/inco.1995.1070 1995

[13] [13]

Learning regular omega languages

Angluin D, Fisman D. Learning regular omega languages. Theor . Comput. Sci., 2016. 650:57–72. doi: 10.1016/j.tcs.2016.07.031. URL https://doi.org/10.1016/j.tcs.2016.07.031

work page doi:10.1016/j.tcs.2016.07.031 2016

[14] [14]

Don’t Care Words with an Application to the Automata-Based Approach for Real Addition

Eisinger J, Klaedtke F. Don’t Care Words with an Application to the Automata-Based Approach for Real Addition. In: Computer Aided Verification, 18th International Conference, CA V 2006, volume 4144 of Lecture Notes in Computer Science . Springer. ISBN 3-540-37406-X, 2006 pp. 67–80. doi: 10.1007/11817963. URL https://doi.org/10.1007/11817963

work page doi:10.1007/11817963 2006

[15] [15]

Regular omega-Languages with an Informative Right Congruence

Angluin D, Fisman D. Regular omega-Languages with an Informative Right Congruence. Electronic Proceedings in Theoretical Computer Science , 2018. 277:265–279. doi:10.4204/eptcs.277.19. URL http://dx.doi.org/10.4204/EPTCS.277.19

work page doi:10.4204/eptcs.277.19 2018

[16] [16]

Computing the Rabin Index of a Parity Automaton

Carton O, Maceiras R. Computing the Rabin Index of a Parity Automaton. RAIRO Theoretical Informatics and Applications, 1999. 33(6):495–506. 88 C. L ¨oding and M.P . Stachon/ Minimization and Learning of ω-Automata with Don’t Cares

work page 1999

[17] [17]

New Optimizations and Heuristics for Determinization of B ¨uchi Automata

L ¨oding C, Pirogov A. New Optimizations and Heuristics for Determinization of B ¨uchi Automata. In: Proceedings of the 17th International Symposium on Automated Technology for Verification and Analysis (ATV A’19), volume 11781 ofLecture Notes in Computer Science . Springer, 2019

work page 2019

[18] [18]

Constructing Deterministic ω-Automata from Examples by an Extension of the RPNI Algorithm

Bohn L, L ¨oding C. Constructing Deterministic ω-Automata from Examples by an Extension of the RPNI Algorithm. In: 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, volume 202 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f ¨ur Informatik, 2021 pp. 20:1–20:18. doi:10.4230/LIPIcs.MFCS.2021.20. URL https://doi.org/10.4...

work page doi:10.4230/lipics.mfcs.2021.20 2021

[19] [19]

Polynomial Identification of omega-Automata

Angluin D, Fisman D, Shoval Y . Polynomial Identification of omega-Automata. CoRR, 2022. abs/2209.09336. doi:10.48550/arXiv.2209.09336. 2209.09336, URL https://doi.org/10.48550/ arXiv.2209.09336

work page doi:10.48550/arxiv.2209.09336 2022

[20] [20]

Reducibility among Combinatorial Problems, pp

Karp RM. Reducibility among Combinatorial Problems, pp. 85–103. Springer US, Boston, MA. ISBN 978-1-4684-2001-2, 1972

work page 2001

[21] [21]

Meyer PJ, Sickert S, Luttenberger M. Strix: Explicit Reactive Synthesis Strikes Back! In: Computer Aided Verification - 30th International Conference, CA V 2018, Held as Part of the Federated Logic Conference, FloC 2018, Oxford, UK, July 14-17, 2018, Proceedings, Part I. 2018 pp. 578–586. doi: 10.1007/978-3-319-96145-3 \ 31. URL https://doi.org/10.1007/97...

work page doi:10.1007/978-3-319-96145-3 2018