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

DOI10.1145/2603088.2603135zbMATH Open1401.68079OpenAlexW2073997125MaRDI QIDQ4635643FDOQ4635643

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

constraint satisfaction problemsdescriptive complexity theoryTuring machinessets with atoms

Mathematics Subject Classification ID

Descriptive complexity and finite models (68Q19)

Cited In (7)

• Contribution of Warsaw logicians to computational logic
• The Max-Atom Problem and Its Relevance
• Title not available (Why is that?)
• Title not available (Why is that?)
• Working with ARMs: Complexity results on atomic representations of Herbrand models
• General lower bounds and improved algorithms for infinite-domain CSPs
• A Dichotomy for First-Order Reducts of Unary Structures

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635643)