@inbook{NevatiaMonmege:ATVA:2023,
    issn = {1611-3349},
    url = {http://dx.doi.org/10.1007/978-3-031-45329-8_6},
    doi = {10.1007/978-3-031-45329-8_6},
    publisher = {Springer Nature Switzerland},
    author = {Nevatia, Dhruv and Monmege, Benjamin},
    year = {2023},
    editor="Andr{\'e}, {\'E}tienne and Sun, Jun",
    title="An Automata Theoretic Characterization of Weighted First-Order Logic",
    booktitle="Automated Technology for Verification and Analysis",
    address="Cham",
    pages="115--133",
    abstract="Since the 1970s with the work of McNaughton, Papert and Sch{\"u}tzenberger [21, 23], a regular language is known to be definable in the first-order logic if and only if its syntactic monoid is aperiodic. This algebraic characterisation of a fundamental logical fragment has been extended in the quantitative case by Droste and Gastin [10], dealing with polynomially ambiguous weighted automata and a restricted fragment of weighted first-order logic. In the quantitative setting, the full weighted first-order logic (without the restriction that Droste and Gastin use, about the quantifier alternation) is more powerful than weighted automata, and extensions of the automata with two-way navigation, and pebbles or nested capabilities have been introduced to deal with it [5, 19]. In this work, we characterise the fragment of these extended weighted automata that recognise exactly the full weighted first-order logic, under the condition that automata are polynomially ambiguous.",
    isbn="978-3-031-45329-8",
    date-added = {2024-5-21 17:27:33 +0100}
}

@inbook{NevatiaMonmege:ATVA:2023, issn = {1611-3349}, url = {http://dx.doi.org/10.1007/978-3-031-45329-8_6}, doi = {10.1007/978-3-031-45329-8_6}, publisher = {Springer Nature Switzerland}, author = {Nevatia, Dhruv and Monmege, Benjamin}, year = {2023}, editor="Andr{\'e}, {\'E}tienne and Sun, Jun", title="An Automata Theoretic Characterization of Weighted First-Order Logic", booktitle="Automated Technology for Verification and Analysis", address="Cham", pages="115--133", abstract="Since the 1970s with the work of McNaughton, Papert and Sch{\"u}tzenberger [21, 23], a regular language is known to be definable in the first-order logic if and only if its syntactic monoid is aperiodic. This algebraic characterisation of a fundamental logical fragment has been extended in the quantitative case by Droste and Gastin [10], dealing with polynomially ambiguous weighted automata and a restricted fragment of weighted first-order logic. In the quantitative setting, the full weighted first-order logic (without the restriction that Droste and Gastin use, about the quantifier alternation) is more powerful than weighted automata, and extensions of the automata with two-way navigation, and pebbles or nested capabilities have been introduced to deal with it [5, 19]. In this work, we characterise the fragment of these extended weighted automata that recognise exactly the full weighted first-order logic, under the condition that automata are polynomially ambiguous.", isbn="978-3-031-45329-8", date-added = {2024-5-21 17:27:33 +0100} }