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

DOI10.1145/2603088.2603135MaRDI QIDQ4635643zbMATH OpenOpenAlexFDO

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

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 theorysets with atomsTuring machines

Mathematics Subject Classification ID

Descriptive complexity and finite models (68Q19)

Recommendations

• Turing machines with atoms
• Locally finite constraint satisfaction problems
• Choiceless polynomial time
• scientific article; zbMATH DE number 4106276
• On polynomial time computation over unordered structures

Cited in

(9)

• Working with ARMs: Complexity results on atomic representations of Herbrand models
• 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
• The language of stratified sets is confluent and strongly normalising
• scientific article; zbMATH DE number 7147443 (Why is no real title available?)
• Turing machines with atoms
• The Max-Atom Problem and Its Relevance
• Orbit-finite linear programming

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)