@inproceedings{10.1145/3209108.3209168,
    Abstract = {It was recently shown by van den Broeck at al. that the symmetric weighted first-order model counting problem (WFOMC) for sentences of two-variable logic FO2 is in polynomial time, while it is \#P1-complete for some FO3-sentences. We extend the result for FO2 in two independent directions: to sentences of the form φ∧∀x∃=1 y ψ (x, y) with φ and ψ formulated in FO2 and to sentences of the uniform one-dimensional fragment U1 of FO, a recently introduced extension of two-variable logic with the capacity to deal with relation symbols of all arities. We note that the former generalizes the extension of FO2 with a functional relation symbol. We also identify a complete classification of first-order prefix classes according to whether WFOMC is in polynomial time or \#P1-complete.},
    Address = {New York, NY, USA},
    Author = {Kuusisto, Antti and Lutz, Carsten},
    BookTitle = {Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science},
    File = {Weighted model counting beyond two-variable logic - proceedings\_paper\_722.pdf},
    ISBN = {9781450355834},
    Keywords = {enumerative combinatorics, two-variable logic, tractability, weighted model counting},
    Location = {Oxford, United Kingdom},
    Pages = {619--628},
    Publisher = {Association for Computing Machinery},
    Series = {LICS '18},
    Title = {Weighted Model Counting beyond Two-Variable Logic},
    URL = {https://doi.org/10.1145/3209108.3209168},
    Year = {2018},
    bdsk-url-1 = {https://doi.org/10.1145/3209108.3209168},
    date-added = {2023-07-06 07:40:43 +0200},
    date-modified = {2023-07-06 07:40:43 +0200},
    numpages = {10},
    doi = {10.1145/3209108.3209168}
}

@inproceedings{10.1145/3209108.3209168, Abstract = {It was recently shown by van den Broeck at al. that the symmetric weighted first-order model counting problem (WFOMC) for sentences of two-variable logic FO2 is in polynomial time, while it is #P1-complete for some FO3-sentences. We extend the result for FO2 in two independent directions: to sentences of the form φ∧∀x∃=1 y ψ (x, y) with φ and ψ formulated in FO2 and to sentences of the uniform one-dimensional fragment U1 of FO, a recently introduced extension of two-variable logic with the capacity to deal with relation symbols of all arities. We note that the former generalizes the extension of FO2 with a functional relation symbol. We also identify a complete classification of first-order prefix classes according to whether WFOMC is in polynomial time or #P1-complete.}, Address = {New York, NY, USA}, Author = {Kuusisto, Antti and Lutz, Carsten}, BookTitle = {Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science}, File = {Weighted model counting beyond two-variable logic - proceedings_paper_722.pdf}, ISBN = {9781450355834}, Keywords = {enumerative combinatorics, two-variable logic, tractability, weighted model counting}, Location = {Oxford, United Kingdom}, Pages = {619--628}, Publisher = {Association for Computing Machinery}, Series = {LICS '18}, Title = {Weighted Model Counting beyond Two-Variable Logic}, URL = {https://doi.org/10.1145/3209108.3209168}, Year = {2018}, bdsk-url-1 = {https://doi.org/10.1145/3209108.3209168}, date-added = {2023-07-06 07:40:43 +0200}, date-modified = {2023-07-06 07:40:43 +0200}, numpages = {10}, doi = {10.1145/3209108.3209168} }