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

DOI10.1145/2603088.2603135zbMATH Open1401.68079OpenAlexW2073997125MaRDI QIDQ4635643FDOQ4635643

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

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

zbMATH Keywords

constraint satisfaction problemsdescriptive complexity theoryTuring machinessets with atoms

Mathematics Subject Classification ID

Descriptive complexity and finite models (68Q19)

Cited In (8)

• Contribution of Warsaw logicians to computational logic
• The Max-Atom Problem and Its Relevance
• A dichotomy for first-order reducts of unary structures
• Title not available (Why is that?)
• The language of stratified sets is confluent and strongly normalising
• Working with ARMs: Complexity results on atomic representations of Herbrand models
• General lower bounds and improved algorithms for infinite-domain CSPs
• Turing machines with atoms

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)