Search results for "PSPACE-completeness"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
57	Wolfgang Slany	The Complexity of Graph Ramsey Games.	Computers and Games	2000	DBLP DOI BibTeX RDF	combinatorial games, graph Ramsey theory, Ramsey game, winning strategy, achievement game, avoidance game, the game of Sim, endgames, complexity, Java applet, edge coloring, PSPACE-completeness
45	Paul Hunter, Anuj Dawar	Complexity Bounds for Regular Games.	MFCS	2005	DBLP DOI BibTeX RDF
44	Alexander Hertel, Alasdair Urquhart	Game Characterizations and the PSPACE-Completeness of Tree Resolution Space.	CSL	2007	DBLP DOI BibTeX RDF
34	Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, Christos H. Papadimitriou	The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies.	ICALP (1)	2006	DBLP DOI BibTeX RDF
34	Petr Jancar	Strong Bisimilarity on Basic Parallel Processes is PSPACE-complete.	LICS	2003	DBLP DOI BibTeX RDF
33	Helmut Alt, Christian Knauer, Günter Rote, Sue Whitesides	The complexity of (un)folding.	SCG	2003	DBLP DOI BibTeX RDF	linkage reconfiguration, computational geometry, PSPACE-completeness
33	Chin Soon Lee, Neil D. Jones, Amir M. Ben-Amram	The size-change principle for program termination.	POPL	2001	DBLP DOI BibTeX RDF	omega automaton, program analysis, termination, partial evaluation, PSPACE-completeness
30	Christel Baier, Tomás Brázdil, Marcus Größer, Antonín Kucera 0001	Stochastic Game Logic.	QEST	2007	DBLP DOI BibTeX RDF
29	Laura Bozzelli, Angelo Montanari, Adriano Peron, Pietro Sala	Pspace-completeness of the temporal logic of sub-intervals and suffixes.	Inf. Comput.	2023	DBLP DOI BibTeX RDF
29	Erik D. Demaine, Robert A. Hearn, Dylan H. Hendrickson, Jayson Lynch	PSPACE-Completeness of Reversible Deterministic Systems.	CoRR	2022	DBLP DOI BibTeX RDF
29	Erik D. Demaine, Robert A. Hearn, Dylan H. Hendrickson, Jayson Lynch	PSPACE-Completeness of Reversible Deterministic Systems.	MCU	2022	DBLP DOI BibTeX RDF
29	Joshua Ani, Lily Chung, Erik D. Demaine, Yevhenii Diomidov, Dylan H. Hendrickson, Jayson Lynch	Pushing Blocks via Checkable Gadgets: PSPACE-Completeness of Push-1F and Block/Box Dude.	FUN	2022	DBLP DOI BibTeX RDF
29	Laura Bozzelli, Angelo Montanari, Adriano Peron, Pietro Sala	Pspace-Completeness of the Temporal Logic of Sub-Intervals and Suffixes.	TIME	2021	DBLP DOI BibTeX RDF
29	Joshua Ani, Sualeh Asif, Erik D. Demaine, Yevhenii Diomidov, Dylan H. Hendrickson, Jayson Lynch, Sarah Scheffler, Adam Suhl	PSPACE-completeness of Pulling Blocks to Reach a Goal.	J. Inf. Process.	2020	DBLP DOI BibTeX RDF
29	Eurinardo Rodrigues Costa, Victor Lage Pessoa, Rudini M. Sampaio, Ronan Soares	PSPACE-completeness of two graph coloring games.	Theor. Comput. Sci.	2020	DBLP DOI BibTeX RDF
29	Joshua Ani, Sualeh Asif, Erik D. Demaine, Yevhenii Diomidov, Dylan H. Hendrickson, Jayson Lynch, Sarah Scheffler, Adam Suhl	PSPACE-completeness of Pulling Blocks to Reach a Goal.	CoRR	2020	DBLP BibTeX RDF
29	Guanjun Liu	PSPACE-Completeness of the Soundness Problem of Safe Asymmetric-Choice Workflow Nets.	Petri Nets	2020	DBLP DOI BibTeX RDF
29	Rémi Nollet, Alexis Saurin, Christine Tasson	PSPACE-Completeness of a Thread Criterion for Circular Proofs in Linear Logic with Least and Greatest Fixed Points.	TABLEAUX	2019	DBLP DOI BibTeX RDF
29	Davide Tateo, Jacopo Banfi, Alessandro Riva, Francesco Amigoni, Andrea Bonarini	Multiagent Connected Path Planning: PSPACE-Completeness and How to Deal With It.	AAAI	2018	DBLP DOI BibTeX RDF
29	Davide Bilò, Luciano Gualà, Stefano Leucci 0001, Guido Proietti, Mirko Rossi	On the PSPACE-completeness of Peg Duotaire and other Peg-Jumping Games.	FUN	2018	DBLP DOI BibTeX RDF
29	Eric Goles 0001, Pedro Montealegre 0001, Ville Salo, Ilkka Törmä	PSPACE-completeness of majority automata networks.	Theor. Comput. Sci.	2016	DBLP DOI BibTeX RDF
29	Eric Goles Ch., Pedro Montealegre 0001, Ville Salo, Ilkka Törmä	PSPACE-Completeness of Majority Automata Networks.	CoRR	2015	DBLP BibTeX RDF
29	Edouard Bonnet, Florian Jamain, Abdallah Saffidine	Draws, Zugzwangs, and PSPACE-Completeness in the Slither Connection Game.	ACG	2015	DBLP DOI BibTeX RDF
29	Maria I. Andreou, Dimitris Fotakis 0001, Vicky Papadopoulou Lesta, Sotiris E. Nikoletseas, Paul G. Spirakis	On Radiocoloring Hierarchically Specified Planar Graphs: PSPACE -completeness and Approximations.	Algorithms, Probability, Networks, and Games	2015	DBLP DOI BibTeX RDF
29	Tom C. van der Zanden, Hans L. Bodlaender	PSPACE-Completeness of Bloxorz and of Games with 2-Buttons.	CIAC	2015	DBLP DOI BibTeX RDF
29	Tom C. van der Zanden, Hans L. Bodlaender	PSPACE-completeness of Bloxorz and of Games with 2-Buttons.	CoRR	2014	DBLP BibTeX RDF
29	John M. Hitchcock, Aduri Pavan	Length-Increasing Reductions for PSPACE-Completeness.	MFCS	2013	DBLP DOI BibTeX RDF
29	Daniel Kirsten	Decidability, undecidability, and PSPACE-completeness of the twins property in the tropical semiring.	Theor. Comput. Sci.	2012	DBLP DOI BibTeX RDF
29	Yasuhiko Takenaga, Hikari Mori, Shigeki Iwata	Stonehenge: Outcome of All First Moves and PSPACE-Completeness.	J. Int. Comput. Games Assoc.	2010	DBLP DOI BibTeX RDF
29	Philipp Hertel, Toniann Pitassi	The PSPACE-Completeness of Black-White Pebbling.	SIAM J. Comput.	2010	DBLP DOI BibTeX RDF
29	Paul S. Bonsma, Luis Cereceda	Finding Paths between graph colourings: PSPACE-completeness and superpolynomial distances.	Theor. Comput. Sci.	2009	DBLP DOI BibTeX RDF
29	Yasuhiko Takenaga, Shigeru Arai	PSPACE-completeness of an escape problem.	Inf. Process. Lett.	2008	DBLP DOI BibTeX RDF
29	Philipp Hertel, Toniann Pitassi	Exponential Time/Space Speedups for Resolution and the PSPACE-completeness of Black-White Pebbling.	FOCS	2007	DBLP DOI BibTeX RDF
29	Paul S. Bonsma, Luis Cereceda	Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances.	MFCS	2007	DBLP DOI BibTeX RDF	vertex-recolouring, colour graph, superpolynomial distance, PSPACE-complete
29	Dimitris Fotakis 0001, Sotiris E. Nikoletseas, Vicky G. Papadopoulou, Paul G. Spirakis	Radiocolorings in periodic planar graphs: PSPACE-completeness and efficient approximations for the optimal range of frequencies.	J. Discrete Algorithms	2006	DBLP DOI BibTeX RDF
29	Kurt Rohloff, Stéphane Lafortune	PSPACE-completeness of Modular Supervisory Control Problems*.	Discret. Event Dyn. Syst.	2005	DBLP DOI BibTeX RDF	computational complexity, verification, supervisory control, modular systems
29	Robert A. Hearn, Erik D. Demaine	PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation.	Theor. Comput. Sci.	2005	DBLP DOI BibTeX RDF
29	Robert A. Hearn, Erik D. Demaine	PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation	CoRR	2002	DBLP BibTeX RDF
29	Maria I. Andreou, Dimitris Fotakis 0001, Sotiris E. Nikoletseas, Vicky G. Papadopoulou, Paul G. Spirakis	On Radiocoloring Hierarchically Specified Planar Graphs: PSPACE-Completeness and Approximations.	MFCS	2002	DBLP DOI BibTeX RDF
29	Dimitris Fotakis 0001, Sotiris E. Nikoletseas, Vicky G. Papadopoulou, Paul G. Spirakis	Radiocolorings in Periodic Planar Graphs: PSPACE-Completeness and Efficient Approximations for the Optimal Range of Frequencies.	WG	2002	DBLP DOI BibTeX RDF
29	Jean-Camille Birget, Stuart W. Margolis, John C. Meakin, Pascal Weil	PSPACE-Completeness of Certain Algorithmic Problems on the Subgroups of Free Groups.	ICALP	1994	DBLP DOI BibTeX RDF
24	Akitoshi Kawamura, Stephen A. Cook	Complexity theory for operators in analysis.	STOC	2010	DBLP DOI BibTeX RDF	higher-type complexity, second-order polynomials, computational complexity, computable analysis
24	Ke Yang	Integer Circuit Evaluation is PSPACE-Complete.	CCC	2000	DBLP DOI BibTeX RDF	Integer Circuit, Chinese Remainder Theorem, PSPACE
24	Michael J. Wooldridge, Paul E. Dunne	Optimistic and Disjunctive Agent Design Problems.	ATAL	2000	DBLP DOI BibTeX RDF
20	José L. Balcázar	The Complexity of Searching Succinctly Represented Graphs.	ICALP	1995	DBLP DOI BibTeX RDF
15	Michael Schmidt 0002, Michael Meier 0002, Georg Lausen	Foundations of SPARQL query optimization.	ICDT	2010	DBLP DOI BibTeX RDF	SPARQL algebra, complexity, query optimization, RDF, SPARQL, semantic query optimization
15	Julien Cristau, Florian Horn 0001	On Reachability Games of Ordinal Length.	SOFSEM	2008	DBLP DOI BibTeX RDF
15	Marco Cadoli, Thomas Eiter, Georg Gottlob	Complexity of propositional nested circumscription and nested abnormality theories.	ACM Trans. Comput. Log.	2005	DBLP DOI BibTeX RDF	Horn theories, nested abnormality theories, computational complexity, nonmonotonic reasoning, knowledge representation and reasoning, Circumscription
15	Jirí Srba	Timed-Arc Petri Nets vs. Networks of Timed Automata.	ICATPN	2005	DBLP DOI BibTeX RDF
15	Bernhard Schwarz	The Complexity of Satisfiability Problems over Finite Lattices.	STACS	2004	DBLP DOI BibTeX RDF
15	Thomas Brihaye, Véronique Bruyère, Jean-François Raskin	Model-Checking for Weighted Timed Automata.	FORMATS/FTRTFT	2004	DBLP DOI BibTeX RDF
15	Uwe Egly	Embedding Lax Logic into Intuitionistic Logic.	CADE	2002	DBLP DOI BibTeX RDF
15	Volker Diekert, Anca Muscholl	Solvability of Equations in Free Partially Commutative Groups Is Decidable.	ICALP	2001	DBLP DOI BibTeX RDF