Turing machines with atoms, constraint satisfaction problems, and descriptive complexity

DOI10.1145/2603088.2603135zbMath1401.68079OpenAlexW2073997125MaRDI QIDQ4635643

Szymon Toruńczyk, Sławomir Lasota, Joanna Ochremiak, Bartek Klin

Publication date: 23 April 2018

Published in: Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.696.83

zbMATH Keywords

Turing machinesconstraint satisfaction problemsdescriptive complexity theorysets with atoms

Mathematics Subject Classification ID

Descriptive complexity and finite models (68Q19)

Related Items (5)

Unnamed Item ⋮ Contribution of Warsaw logicians to computational logic ⋮ General lower bounds and improved algorithms for infinite-domain CSPs ⋮ A Dichotomy for First-Order Reducts of Unary Structures ⋮ Unnamed Item

This page was built for publication: Turing machines with atoms, constraint satisfaction problems, and descriptive complexity