@inbook{Li2018,
    Abstract = {Complementing B{\"u}chi automata is an intriguing and intensively studied problem. Complementation suffers from a theoretical super-exponential complexity. From an applied point of view, however, there is no reason to assume that the target language is more complex than the source language. The chance that the smallest representation of a complement language is (much) smaller or (much) larger than the representation of its source should be the same; after all, complementing twice is an empty operation. With this insight, we study the use of learning for complementation. We use a recent learning approach for FDFAs, families of DFAs, that can be used to represent {\$}{\$}{\backslash}omega {\$}{\$} -regular languages, as a basis for our complementation technique. As a surprising result, it has proven beneficial not to learn an FDFA that represents the complement language of a B{\"u}chi automaton (or the language itself, as complementing FDFAs is cheap), but to use it as an intermediate construction in the learning cycle. While the FDFA is refined in every step, the target is an associated B{\"u}chi automaton that underestimates the language of a conjecture FDFA. We have implemented our approach and compared it on benchmarks against the algorithms provided in GOAL. The complement automata we produce for large B{\"u}chi automata are generally smaller, which makes them more valuable for applications like model checking. Our approach has also been faster in 98{\\%} of the cases. Finally we compare the advantages we gain by the novel techniques with advantages provided by the high level optimisations implemented in the state-of-the-art tool SPOT.},
    Address = {Cham},
    Author = {Li, Yong and Turrini, Andrea and Zhang, Lijun and Schewe, Sven},
    BookTitle = {Verification, Model Checking, and Abstract Interpretation: 19th International Conference, VMCAI 2018, Los Angeles, CA, USA, January 7-9, 2018, Proceedings},
    Editor = {Dillig, Isil and Palsberg, Jens},
    File = {vmcai18 (0) - a - a - n.pdf},
    ISBN = {978-3-319-73721-8},
    Keywords = {citesme!},
    Pages = {313--335},
    Publisher = {Springer International Publishing},
    Title = {Learning to Complement B{\"u}chi Automata},
    URL = {https://doi.org/10.1007/978-3-319-73721-8\_15},
    Year = {2018},
    bdsk-url-1 = {https://doi.org/10.1007/978-3-319-73721-8\_15},
    date-added = {2018-01-09 08:28:28 +0000},
    date-modified = {2018-01-09 08:28:42 +0000},
    doi = {10.1007/978-3-319-73721-8_15}
}

@inbook{Li2018, Abstract = {Complementing B{\"u}chi automata is an intriguing and intensively studied problem. Complementation suffers from a theoretical super-exponential complexity. From an applied point of view, however, there is no reason to assume that the target language is more complex than the source language. The chance that the smallest representation of a complement language is (much) smaller or (much) larger than the representation of its source should be the same; after all, complementing twice is an empty operation. With this insight, we study the use of learning for complementation. We use a recent learning approach for FDFAs, families of DFAs, that can be used to represent {\$}{\$}{\backslash}omega {\$}{\$} -regular languages, as a basis for our complementation technique. As a surprising result, it has proven beneficial not to learn an FDFA that represents the complement language of a B{\"u}chi automaton (or the language itself, as complementing FDFAs is cheap), but to use it as an intermediate construction in the learning cycle. While the FDFA is refined in every step, the target is an associated B{\"u}chi automaton that underestimates the language of a conjecture FDFA. We have implemented our approach and compared it on benchmarks against the algorithms provided in GOAL. The complement automata we produce for large B{\"u}chi automata are generally smaller, which makes them more valuable for applications like model checking. Our approach has also been faster in 98{\%} of the cases. Finally we compare the advantages we gain by the novel techniques with advantages provided by the high level optimisations implemented in the state-of-the-art tool SPOT.}, Address = {Cham}, Author = {Li, Yong and Turrini, Andrea and Zhang, Lijun and Schewe, Sven}, BookTitle = {Verification, Model Checking, and Abstract Interpretation: 19th International Conference, VMCAI 2018, Los Angeles, CA, USA, January 7-9, 2018, Proceedings}, Editor = {Dillig, Isil and Palsberg, Jens}, File = {vmcai18 (0) - a - a - n.pdf}, ISBN = {978-3-319-73721-8}, Keywords = {citesme!}, Pages = {313--335}, Publisher = {Springer International Publishing}, Title = {Learning to Complement B{\"u}chi Automata}, URL = {https://doi.org/10.1007/978-3-319-73721-8_15}, Year = {2018}, bdsk-url-1 = {https://doi.org/10.1007/978-3-319-73721-8_15}, date-added = {2018-01-09 08:28:28 +0000}, date-modified = {2018-01-09 08:28:42 +0000}, doi = {10.1007/978-3-319-73721-8_15} }