On computability and tractability for infinite sets

DOI10.1145/3209108.3209190MaRDI QIDQ5145286zbMATH OpenOpenAlexFDO

Authors Mikołaj Bojańczyk, Szymon Toruńczyk

Publication date 20 January 2021

Published in Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3209108.3209190

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• ON THE COMPUTING POWER OF PROGRAMS WITH SETS
• Choiceless polynomial time
• Predicatively computable functions on sets
• Definability of Cai-Fürer-Immerman Problems in Choiceless Polynomial Time
• Cobham recursive set functions

Cited in

(10)

• Reasoning about infinite computations
• Linear ordering on graphs, anti-founded sets and polynomial time computability
• Permutation groups with small orbit growth
• Infinite computations and the generic finite
• The Complexity of Infinite Computations In Models of Set Theory
• Choiceless computation and symmetry
• ON THE COMPUTING POWER OF PROGRAMS WITH SETS
• Residuality and learning for nondeterministic nominal automata
• scientific article; zbMATH DE number 7559500 (Why is no real title available?)
• Orbit-finite linear programming

This page was built for publication: On computability and tractability for infinite sets

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