Computational complexity of computing symmetries in finite-domain planning

DOI10.1613/JAIR.1.12283MaRDI QIDQ5856495zbMATH OpenOpenAlexWikidataFDO

Authors Alexander Shleyfman, Peter Jonsson

Publication date 26 March 2021

Published in Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1613/jair.1.12283

zbMATH Keywords

mathematical foundationsplanning

Mathematics Subject Classification ID

Artificial intelligence (68Txx)

Recommendations

• State-variable planning under structural restrictions: algorithms and complexity
• Computational complexity of the place/transition-net symmetry reduction method
• Time and Space Bounds for Planning
• The computational complexity of propositional STRIPS planning
• On the constructive orbit problem

Cites work

• A compact representation for permutation groups
• A congruence theorem for trees
• A note on the graph isomorphism counting problem
• Automatically generating abstractions for planning
• CNF and DNF succinct graph encodings
• Concise finite-domain representations for PDDL planning tasks
• Downward refinement and the efficiency of hierarchical problem solving
• Graph isomorphism in quasipolynomial time (extended abstract)
• Graph isomorphism problem
• scientific article; zbMATH DE number 5995471 (Why is no real title available?)
• scientific article; zbMATH DE number 4213468 (Why is no real title available?)
• scientific article; zbMATH DE number 4007728 (Why is no real title available?)
• scientific article; zbMATH DE number 3575612 (Why is no real title available?)
• scientific article; zbMATH DE number 1946870 (Why is no real title available?)
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• On the complexity of k-SAT
• On the Structure of Polynomial Time Reducibility
• Permutation Groups and the Graph Isomorphism Problem
• Planning over chain causal graphs for variables with domains of size 5 is NP-hard
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Strong bounds on the approximability of two Pspace-hard problems in propositional planning
• Time and Space Bounds for Planning
• Towards efficient universal planning: A randomized approach
• Tractable plan existence does not imply tractable plan generation

This page was built for publication: Computational complexity of computing symmetries in finite-domain planning

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