@article{Mottet:2020aa,
    Abstract = {We investigate the complexity of the containment problem ``Does L(A)⊆L(B){\$}L({$\backslash$}mathcal {\{}A{\}}){$\backslash$}subseteq L({\{}{$\backslash$}mathscr{\{}B{\}}{\}}){\$}hold?''for register automata and timed automata, where B{\$}{\{}{$\backslash$}mathscr{\{}B{\}}{\}}{\$}is assumed to be unambiguous and A{\$}{$\backslash$}mathcal {\{}A{\}}{\$}is arbitrary. We prove that the problem is decidable in the case of register automata over (ℕ,=){\$}({$\backslash$}mathbb N,=){\$}, in the case of register automata over (ℚ,<){\$}({$\backslash$}mathbb Q,<){\$}when B{\$}{\{}{$\backslash$}mathscr{\{}B{\}}{\}}{\$}has a single register, and in the case of timed automata when B{\$}{\{}{$\backslash$}mathscr{\{}B{\}}{\}}{\$}has a single clock. We give a 2-EXPSPACE algorithm in the first case, whose complexity is a single exponential in the case that B{\$}{\{}{$\backslash$}mathscr{\{}B{\}}{\}}{\$}has a bounded number of registers. In the other cases, we give an EXPSPACE algorithm.},
    Author = {Mottet, Antoine and Quaas, Karin},
    File = {The Containment Problem for Unambiguous Register Automata and Unambiguous Timed Automata - Mottet-Quaas2020\_Article\_TheContainmentProblemForUnambi0 - g.pdf},
    ISBN = {1433-0490},
    Journal = {Theory of Computing Systems},
    Title = {The Containment Problem for Unambiguous Register Automata and Unambiguous Timed Automata},
    URL = {https://doi.org/10.1007/s00224-020-09997-2},
    Year = {2020},
    bdsk-url-1 = {https://doi.org/10.1007/s00224-020-09997-2},
    da = {2020/09/15},
    date-added = {2021-02-17 12:54:41 +0100},
    date-modified = {2021-02-17 12:54:41 +0100},
    id = {Mottet2020},
    ty = {JOUR},
    doi = {10.1007/s00224-020-09997-2}
}

@article{Mottet:2020aa, Abstract = {We investigate the complexity of the containment problem ``Does L(A)⊆L(B){\$}L({$\backslash$}mathcal {{}A{}}){$\backslash$}subseteq L({{}{$\backslash$}mathscr{{}B{}}{}}){\$}hold?''for register automata and timed automata, where B{\$}{{}{$\backslash$}mathscr{{}B{}}{}}{\$}is assumed to be unambiguous and A{\$}{$\backslash$}mathcal {{}A{}}{\$}is arbitrary. We prove that the problem is decidable in the case of register automata over (ℕ,=){\$}({$\backslash$}mathbb N,=){\$}, in the case of register automata over (ℚ,<){\$}({$\backslash$}mathbb Q,<){\$}when B{\$}{{}{$\backslash$}mathscr{{}B{}}{}}{\$}has a single register, and in the case of timed automata when B{\$}{{}{$\backslash$}mathscr{{}B{}}{}}{\$}has a single clock. We give a 2-EXPSPACE algorithm in the first case, whose complexity is a single exponential in the case that B{\$}{{}{$\backslash$}mathscr{{}B{}}{}}{\$}has a bounded number of registers. In the other cases, we give an EXPSPACE algorithm.}, Author = {Mottet, Antoine and Quaas, Karin}, File = {The Containment Problem for Unambiguous Register Automata and Unambiguous Timed Automata - Mottet-Quaas2020_Article_TheContainmentProblemForUnambi0 - g.pdf}, ISBN = {1433-0490}, Journal = {Theory of Computing Systems}, Title = {The Containment Problem for Unambiguous Register Automata and Unambiguous Timed Automata}, URL = {https://doi.org/10.1007/s00224-020-09997-2}, Year = {2020}, bdsk-url-1 = {https://doi.org/10.1007/s00224-020-09997-2}, da = {2020/09/15}, date-added = {2021-02-17 12:54:41 +0100}, date-modified = {2021-02-17 12:54:41 +0100}, id = {Mottet2020}, ty = {JOUR}, doi = {10.1007/s00224-020-09997-2} }