@article{doi:10.1002/malq.201700055,
    Abstract = {Abstract We consider two-variable, first-order logic in which a single distinguished predicate is required to be interpreted as a transitive relation. We show that the finite satisfiability problem for this logic is decidable in triply exponential non-deterministic time. Complexity falls to doubly exponential non-deterministic time if the transitive relation is constrained to be a partial order.},
    Author = {Pratt-Hartmann, Ian},
    EPrint = {https://onlinelibrary.wiley.com/doi/pdf/10.1002/malq.201700055},
    File = {Pratt-Hartmann-2018-Mathematical\_Logic\_Quarterly (0) - a - a - i.pdf},
    Journal = {Mathematical Logic Quarterly},
    Number = {3},
    Pages = {218-248},
    Title = {Finite satisfiability for two-variable, first-order logic with one transitive relation is decidable},
    URL = {https://onlinelibrary.wiley.com/doi/abs/10.1002/malq.201700055},
    Volume = {64},
    bdsk-url-1 = {https://onlinelibrary.wiley.com/doi/abs/10.1002/malq.201700055},
    bdsk-url-2 = {https://doi.org/10.1002/malq.201700055},
    date-added = {2018-10-05 09:13:25 +0000},
    date-modified = {2018-10-05 09:13:25 +0000},
    doi = {10.1002/malq.201700055}
}

@article{doi:10.1002/malq.201700055, Abstract = {Abstract We consider two-variable, first-order logic in which a single distinguished predicate is required to be interpreted as a transitive relation. We show that the finite satisfiability problem for this logic is decidable in triply exponential non-deterministic time. Complexity falls to doubly exponential non-deterministic time if the transitive relation is constrained to be a partial order.}, Author = {Pratt-Hartmann, Ian}, EPrint = {https://onlinelibrary.wiley.com/doi/pdf/10.1002/malq.201700055}, File = {Pratt-Hartmann-2018-Mathematical_Logic_Quarterly (0) - a - a - i.pdf}, Journal = {Mathematical Logic Quarterly}, Number = {3}, Pages = {218-248}, Title = {Finite satisfiability for two-variable, first-order logic with one transitive relation is decidable}, URL = {https://onlinelibrary.wiley.com/doi/abs/10.1002/malq.201700055}, Volume = {64}, bdsk-url-1 = {https://onlinelibrary.wiley.com/doi/abs/10.1002/malq.201700055}, bdsk-url-2 = {https://doi.org/10.1002/malq.201700055}, date-added = {2018-10-05 09:13:25 +0000}, date-modified = {2018-10-05 09:13:25 +0000}, doi = {10.1002/malq.201700055} }