@inproceedings{JeckerMazowieckiPurser:LICS:2024,
    author = {Jecker, Isma\"{e}l and Mazowiecki, Filip and Purser, David},
    title = {Determinisation and Unambiguisation of Polynomially-Ambiguous Rational Weighted Automata},
    year = {2024},
    isbn = {9798400706608},
    publisher = {Association for Computing Machinery},
    address = {New York, NY, USA},
    url = {https://doi.org/10.1145/3661814.3662073},
    doi = {10.1145/3661814.3662073},
    abstract = {We study the determinisation and unambiguisation problems of weighted automata over the field of rationals: Given a weighted automaton, can we determine whether there exists an equivalent deterministic, respectively unambiguous, weighted automaton? Recent results by Bell and Smertnig show that the problem is decidable, however they do not provide any complexity bounds. We show that both problems are in PSPACE for polynomially-ambiguous weighted automata.},
    booktitle = {Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science},
    articleno = {46},
    numpages = {13},
    keywords = {weighted automata, determinisation, unambiguisation},
    location = {Tallinn, Estonia},
    series = {LICS '24},
    date-added = {2025-1-23 10:17:55 +0100}
}

@inproceedings{JeckerMazowieckiPurser:LICS:2024, author = {Jecker, Isma\"{e}l and Mazowiecki, Filip and Purser, David}, title = {Determinisation and Unambiguisation of Polynomially-Ambiguous Rational Weighted Automata}, year = {2024}, isbn = {9798400706608}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, url = {https://doi.org/10.1145/3661814.3662073}, doi = {10.1145/3661814.3662073}, abstract = {We study the determinisation and unambiguisation problems of weighted automata over the field of rationals: Given a weighted automaton, can we determine whether there exists an equivalent deterministic, respectively unambiguous, weighted automaton? Recent results by Bell and Smertnig show that the problem is decidable, however they do not provide any complexity bounds. We show that both problems are in PSPACE for polynomially-ambiguous weighted automata.}, booktitle = {Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science}, articleno = {46}, numpages = {13}, keywords = {weighted automata, determinisation, unambiguisation}, location = {Tallinn, Estonia}, series = {LICS '24}, date-added = {2025-1-23 10:17:55 +0100} }