Search results for "PSPACE-complete"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
65	Robert A. Hearn, Erik D. Demaine	The Nondeterministic Constraint Logic Model of Computation: Reductions and Applications.	ICALP	2002	DBLP DOI BibTeX RDF
58	Stéphane Demri, Denis Lugiez	Presburger Modal Logic Is PSPACE-Complete.	IJCAR	2006	DBLP DOI BibTeX RDF
56	Marco A. Casanova, Ronald Fagin, Christos H. Papadimitriou	Inclusion Dependencies and Their Interaction with Functional Dependencies.	PODS	1982	DBLP DOI BibTeX RDF	relational database, functional dependency, PSPACE-complete, inclusion dependency, complete axiomatization
56	Joachim Niehren, Martin Müller 0001, Jean-Marc Talbot	Entailment of Atomic Set Constraints is PSPACE-Complete.	LICS	1999	DBLP DOI BibTeX RDF
56	Madhav V. Marathe, Harry B. Hunt III, S. S. Ravi	The Complexity of Approximating PSPACE-Complete Problems for Hierarchical Specifications (Extended Abstract).	ICALP	1993	DBLP DOI BibTeX RDF
51	Keijo Heljanko	Model Checking with Finite Complete Prefixes Is PSPACE-Complete.	CONCUR	2000	DBLP DOI BibTeX RDF
46	Marcel Crâsmaru, John Tromp	Ladders Are PSPACE-Complete.	Computers and Games	2000	DBLP DOI BibTeX RDF
46	Marcus Schaefer 0001	Deciding the K-Dimension is PSPACE-Complete.	CCC	2000	DBLP DOI BibTeX RDF	computational complexity, learning theory, PSPACE
46	Ke Yang	Integer Circuit Evaluation is PSPACE-Complete.	CCC	2000	DBLP DOI BibTeX RDF	Integer Circuit, Chinese Remainder Theorem, PSPACE
44	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
42	Thomas Eiter, Georg Gottlob	On the Complexity of Theory Curbing.	LPAR	2000	DBLP DOI BibTeX RDF
39	Krishnendu Chatterjee	Stochastic Müller Games are PSPACE-Complete.	FSTTCS	2007	DBLP DOI BibTeX RDF
37	Felix G. König, Marco E. Lübbecke, Rolf H. Möhring, Guido Schäfer, Ines Spenke	Solutions to Real-World Instances of PSPACE-Complete Stacking.	ESA	2007	DBLP DOI BibTeX RDF
37	Kyle W. Burke, Shang-Hua Teng	A PSPACE-complete Sperner Triangle Game.	WINE	2007	DBLP DOI BibTeX RDF
37	Volker Diekert, Claudio Gutierrez 0001, Christian Hagenah	The Existential Theory of Equations with Rational Constraints in Free Groups is PSPACE-Complete.	STACS	2001	DBLP DOI BibTeX RDF	free group, Formal languages, regular language, equations
37	Stefan Dziembowski	Bounded-Variable Fixpoint Queries are PSPACE-complete.	CSL	1996	DBLP DOI BibTeX RDF
37	Erez Petrank, Gábor Tardos	On the Knowledge Complexity of NP.	Comb.	2002	DBLP DOI BibTeX RDF	AMS Subject Classification (2000) Classes: 68Q15, 68Q17
37	Edith Hemaspaandra	The Complexity of Poor Man's Logic.	STACS	2000	DBLP DOI BibTeX RDF
34	Laura Bozzelli, Salvatore La Torre	Decision Problems for Lower/Upper Bound Parametric Timed Automata.	ICALP	2007	DBLP DOI BibTeX RDF
34	Guoqiang Pan, Moshe Y. Vardi	Fixed-Parameter Hierarchies inside PSPACE.	LICS	2006	DBLP DOI BibTeX RDF
34	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
34	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
32	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
32	Stéphane Demri	LTL over Integer Periodicity Constraints: (Extended Abstract).	FoSSaCS	2004	DBLP DOI BibTeX RDF
32	Christof Löding, Philipp Rohde	Solving the Sabotage Game Is PSPACE-Hard.	MFCS	2003	DBLP DOI BibTeX RDF
32	Marcin Rychlik	On Probabilistic Quantified Satisfability Games.	MFCS	2003	DBLP DOI BibTeX RDF
32	Krishnendu Chatterjee, Di Ma, Rupak Majumdar, Tian Zhao 0002, Thomas A. Henzinger, Jens Palsberg	Stack Size Analysis for Interrupt-Driven Programs.	SAS	2003	DBLP DOI BibTeX RDF
32	T. V. Thirumala Reddy, D. Sai Krishna, C. Pandu Rangan	The Guarding Problem - Complexity and Approximation.	IWOCA	2009	DBLP DOI BibTeX RDF	QBF (Quantified Boolean Formula), QSAT (Quantified Satisfiability), Approximation Algorithms, PSPACE-complete
32	Monika Maidl	The Common Fragment of CTL and LTL.	FOCS	2000	DBLP DOI BibTeX RDF	action-based computation tree logic, linear time logic, common fragment, ACTL formulas, PSPACE-complete problem, path quantifiers, 1-weak Buchi automaton, automaton size, formula size, computational complexity, temporal logic, trees (mathematics), decidability, finite automata, expressive power, negation, CTL, LTL, inductive definition
32	Costas Courcoubetis, Mihalis Yannakakis	The Complexity of Probabilistic Verification.	J. ACM	1995	DBLP DOI BibTeX RDF	EXPTIME-complete, model checking, temporal logic, Markov chain, automata, probabilistic algorithm, PSPACE-complete
32	Rajeev Alur, Thomas A. Henzinger	Back to the Future: Towards a Theory of Timed Regular Languages	FOCS	1992	DBLP DOI BibTeX RDF	theory of timed regular languages, two-way timed automata, temporal logic, undecidability, boolean operations, PSPACE-complete
32	Patrick Lincoln, John C. Mitchell, Andre Scedrov, Natarajan Shankar	Decision Problems for Propositional Linear Logic	FOCS	1990	DBLP DOI BibTeX RDF	noncommutative propositional linear logic, propositional linear logic, multiplicative fragment, unrestricted weakening, NP-completeness, undecidability, decision problem, PSPACE-complete
32	Xiaotie Deng, Christos H. Papadimitriou	Exploring an Unknown Graph (Extended Abstract)	FOCS	1990	DBLP DOI BibTeX RDF	unknown graph exploration, strongly connected graph, Eulerian graphs, bounded ratio, directed graph, PSPACE-complete, worst-case ratio
30	Stéphane Demri, Alexander Rabinovich	The Complexity of Temporal Logic with Until and Since over Ordinals.	LPAR	2007	DBLP DOI BibTeX RDF
30	Paul Hunter, Anuj Dawar	Complexity Bounds for Regular Games.	MFCS	2005	DBLP DOI BibTeX RDF
30	Shin Aida, Marcel Crâsmaru, Kenneth W. Regan, Osamu Watanabe 0001	Games with a Uniqueness Property.	STACS	2002	DBLP DOI BibTeX RDF
30	Hing Leung	On Finite Automata with Limited Nondeterminism.	Acta Informatica	1998	DBLP DOI BibTeX RDF
30	David Lichtenstein, Michael Sipser	GO Is Polynomial-Space Hard.	J. ACM	1980	DBLP DOI BibTeX RDF
29	Salvatore La Torre, Gennaro Parlato	On the Complexity of LtlModel-Checking of Recursive State Machines.	ICALP	2007	DBLP DOI BibTeX RDF
29	John H. Reif, Sudheer Sahu, Peng Yin 0003	Complexity of Graph Self-assembly in Accretive Systems and Self-destructible Systems.	DNA	2005	DBLP DOI BibTeX RDF
29	Stephen D. Travers	The Complexity of Membership Problems for Circuits over Sets of Integers.	MFCS	2004	DBLP DOI BibTeX RDF
27	Alexander Rabinovich	Complexity of Metric Temporal Logics with Counting and the Pnueli Modalities.	FORMATS	2008	DBLP DOI BibTeX RDF
27	Michael Bauland, Thomas Schneider 0002, Henning Schnoor, Ilka Schnoor, Heribert Vollmer	The Complexity of Generalized Satisfiability for Linear Temporal Logic.	FoSSaCS	2007	DBLP DOI BibTeX RDF	computational complexity, linear temporal logic
27	Wiebe van der Hoek, Alessio Lomuscio, Michael J. Wooldridge	On the complexity of practical ATL model checking.	AAMAS	2006	DBLP DOI BibTeX RDF	verification, complexity, cooperation, logic
27	Rajeev Alur, Salvatore La Torre	Deterministic generators and games for Ltl fragments.	ACM Trans. Comput. Log.	2004	DBLP DOI BibTeX RDF	Games, Temporal Logic, Automata
25	Chao Yang, Zhujun Zhang	Friends-and-strangers is PSPACE-complete.	CoRR	2024	DBLP DOI BibTeX RDF
25	Chao Yang, Zhujun Zhang	Atropos-k is PSPACE-complete.	CoRR	2024	DBLP DOI BibTeX RDF
25	Jose Balanza-Martinez, Angel A. Cantu, Robert T. Schweller, Tim Wylie	A Simple Proof that Ricochet Robots is PSPACE-Complete.	CoRR	2024	DBLP DOI BibTeX RDF
25	Sophie Hao	Universal Generation for Optimality Theory Is PSPACE-Complete.	Comput. Linguistics	2024	DBLP DOI BibTeX RDF
25	Md Lutfar Rahman, Thomas Watson 0001	6-Uniform Maker-Breaker Game is PSPACE-Complete.	Comb.	2023	DBLP DOI BibTeX RDF
25	Jan Philipp Wächter, Armin Weiß	An Automaton Group with PSPACE-Complete Word Problem.	Theory Comput. Syst.	2023	DBLP DOI BibTeX RDF
25	Laure Daviaud, David Purser	The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete).	CoRR	2023	DBLP DOI BibTeX RDF
25	Kanae Yoshiwatari, Hironori Kiya, Koki Suetsugu, Tesshu Hanaka, Hirotaka Ono 0001	Turning Tiles is PSPACE-complete.	CoRR	2023	DBLP DOI BibTeX RDF
25	Shankara Narayanan Krishna, Khushraj Nanik Madnani, Rupak Majumdar, Paritosh K. Pandya	Satisfiability Checking of Multi-Variable TPTL with Unilateral Intervals Is PSPACE-Complete.	CoRR	2023	DBLP DOI BibTeX RDF
25	Thomas Depian, Christoph Kern, Sebastian Röder, Soeren Terziadis, Markus Wallinger	Network Navigation with Online Delays is PSPACE-complete.	CoRR	2023	DBLP DOI BibTeX RDF
25	Laure Daviaud, David Purser	The Big-O Problem for Max-Plus Automata is Decidable (PSPACE-Complete).	LICS	2023	DBLP DOI BibTeX RDF
25	Valentin Gledel, Nacim Oijid	Avoidance Games Are PSPACE-Complete.	STACS	2023	DBLP DOI BibTeX RDF
25	Shankara Narayanan Krishna, Khushraj Nanik Madnani, Rupak Majumdar, Paritosh K. Pandya	Satisfiability Checking of Multi-Variable TPTL with Unilateral Intervals Is PSPACE-Complete.	CONCUR	2023	DBLP DOI BibTeX RDF
25	Lear Bahack	The Game of Tumbleweed is PSPACE-complete.	CoRR	2022	DBLP DOI BibTeX RDF
25	Laurent Bartholdi, Michael Figelius, Markus Lohrey, Armin Weiß	Groups with ALOGTIME-hard Word Problems and PSPACE-complete Compressed Word Problems.	ACM Trans. Comput. Theory	2022	DBLP DOI BibTeX RDF
25	Austin Luchsinger	Brief Announcement: Barrier-1 Reachability for Thermodynamic Binding Networks Is PSPACE-Complete.	SAND	2022	DBLP DOI BibTeX RDF
25	Shankaranarayanan Krishna, Adwait Godbole, Roland Meyer 0001, Soham Chakraborty 0001	Parameterized Verification under Release Acquire is PSPACE-complete.	PODC	2022	DBLP DOI BibTeX RDF
25	Bosheng Song, Xiangxiang Zeng	Solving a PSPACE-complete problem by symport/antiport P systems with promoters and membrane division.	J. Membr. Comput.	2021	DBLP DOI BibTeX RDF
25	Kevin Buchin, Mart Hagedoorn, Irina Kostitsyna, Max van Mulken	Dots & Boxes is PSPACE-complete.	CoRR	2021	DBLP BibTeX RDF
25	Erik D. Demaine, Yevhenii Diomidov	Strings-and-Coins and Nimstring are PSPACE-complete.	CoRR	2021	DBLP BibTeX RDF
25	David Caballero, Timothy Gomez, Robert T. Schweller, Tim Wylie	Covert Computation in Staged Self-Assembly: Verification Is PSPACE-Complete.	ESA	2021	DBLP DOI BibTeX RDF
25	Kevin Buchin, Mart Hagedoorn, Irina Kostitsyna, Max van Mulken	Dots & Boxes Is PSPACE-Complete.	MFCS	2021	DBLP DOI BibTeX RDF
25	Md Lutfar Rahman, Thomas Watson 0001	6-Uniform Maker-Breaker Game Is PSPACE-Complete.	STACS	2021	DBLP DOI BibTeX RDF
25	Josh Brunner, Lily Chung, Erik D. Demaine, Dylan H. Hendrickson, Adam Hesterberg, Adam Suhl, Avi Zeff	1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete.	FUN	2021	DBLP DOI BibTeX RDF
25	Parosh Aziz Abdulla, Mohamed Faouzi Atig, Rojin Rezvan	Parameterized verification under TSO is PSPACE-complete.	Proc. ACM Program. Lang.	2020	DBLP DOI BibTeX RDF
25	Md Lutfar Rahman, Thomas Watson 0001	6-Uniform Maker-Breaker Game Is PSPACE-Complete.	Electron. Colloquium Comput. Complex.	2020	DBLP BibTeX RDF
25	Alec Henderson, Radu Nicolescu, Michael J. Dinneen	Solving a PSPACE-complete problem with cP systems.	J. Membr. Comput.	2020	DBLP DOI BibTeX RDF
25	Josh Brunner, Lily Chung, Erik D. Demaine, Dylan H. Hendrickson, Adam Hesterberg, Adam Suhl, Avi Zeff	1 x 1 Rush Hour with Fixed Blocks is PSPACE-complete.	CoRR	2020	DBLP BibTeX RDF
25	William Vega-Brown, Nicholas Roy	Task and Motion Planning Is PSPACE-Complete.	AAAI	2020	DBLP DOI BibTeX RDF
25	Dmitry Chistikov 0001, Grzegorz Lisowski, Mike Paterson, Paolo Turrini	Convergence of Opinion Diffusion is PSPACE-Complete.	AAAI	2020	DBLP DOI BibTeX RDF
25	Jan Philipp Wächter, Armin Weiß	An Automaton Group with PSPACE-Complete Word Problem.	STACS	2020	DBLP DOI BibTeX RDF
25	David Caballero, Angel A. Cantu, Timothy Gomez, Austin Luchsinger, Robert T. Schweller, Tim Wylie	Relocating Units in Robot Swarms with Uniform Control Signals is PSPACE-Complete.	CCCG	2020	DBLP BibTeX RDF
25	Laurent Bartholdi, Michael Figelius, Markus Lohrey, Armin Weiß	Groups with ALOGTIME-Hard Word Problems and PSPACE-Complete Circuit Value Problems.	CCC	2020	DBLP DOI BibTeX RDF
25	Viliam Geffert	Unary Coded PSPACE-Complete Languages in ASPACE(loglog n).	Theory Comput. Syst.	2019	DBLP DOI BibTeX RDF
25	Laurent Bartholdi, Michael Figelius, Markus Lohrey, Armin Weiß	Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems.	CoRR	2019	DBLP BibTeX RDF
25	Jan Philipp Wächter, Armin Weiß	An Automaton Group with PSPACE-Complete Word Problem.	CoRR	2019	DBLP BibTeX RDF
25	Dmitry Chistikov 0001, Grzegorz Lisowski, Mike Paterson, Paolo Turrini	Convergence of Opinion Diffusion is PSPACE-complete.	CoRR	2019	DBLP BibTeX RDF
25	Kyle Burke, Robert A. Hearn	PSPACE-complete two-color planar placement games.	Int. J. Game Theory	2019	DBLP DOI BibTeX RDF
25	Martin Böhm 0001, Pavel Veselý 0001	Online Chromatic Number is PSPACE-Complete.	Theory Comput. Syst.	2018	DBLP DOI BibTeX RDF
25	Parosh Aziz Abdulla, Mohamed Faouzi Atig, Radu Ciobanu, Richard Mayr, Patrick Totzke	Universal Safety for Timed Petri Nets is PSPACE-complete.	CoRR	2018	DBLP BibTeX RDF
25	Jonathan Gabor, Aaron Williams	Switches are PSPACE-Complete.	CCCG	2018	DBLP BibTeX RDF
25	Parosh Aziz Abdulla, Mohamed Faouzi Atig, Radu Ciobanu, Richard Mayr, Patrick Totzke	Universal Safety for Timed Petri Nets is PSPACE-complete.	CONCUR	2018	DBLP DOI BibTeX RDF
25	Tomás Masopust, Markus Krötzsch	Deciding Universality of ptNFAs is PSpace-Complete.	SOFSEM	2018	DBLP DOI BibTeX RDF
25	Kuize Zhang	The problem of determining the weak (periodic) detectability of discrete event systems is PSPACE-complete.	Autom.	2017	DBLP DOI BibTeX RDF
25	Weihua He, Ziwen Liu, Chao Yang 0003	Snowman is PSPACE-complete.	Theor. Comput. Sci.	2017	DBLP DOI BibTeX RDF
25	Viliam Geffert	Unary Coded PSPACE-Complete Languages in ASPACE(loglog n).	CSR	2017	DBLP DOI BibTeX RDF
25	Reino Niskanen	Reachability Problem for Polynomial Iteration Is PSPACE-complete.	RP	2017	DBLP DOI BibTeX RDF
25	Bernd Meyer 0008	Generalized Pete's Pike is PSPACE-complete.	Theor. Comput. Sci.	2016	DBLP DOI BibTeX RDF
25	André Grahl Pereira, Marcus Ritt, Luciana S. Buriol	Pull and PushPull are PSPACE-complete.	Theor. Comput. Sci.	2016	DBLP DOI BibTeX RDF
25	Saeed Akhoondian Amiri, Stephan Kreutzer, Roman Rabinovich 0001	DAG-width is PSPACE-complete.	Theor. Comput. Sci.	2016	DBLP DOI BibTeX RDF
25	Markus Steindl	On semigroups with PSPACE-complete subpower membership problem.	CoRR	2016	DBLP BibTeX RDF
25	Kyle Burke, Bob Hearn	PSPACE-Complete Two-Color Placement Games.	CoRR	2016	DBLP BibTeX RDF
25	Willem Heijltjes, Robin Houston 0001	Proof equivalence in MLL is PSPACE-complete.	Log. Methods Comput. Sci.	2016	DBLP DOI BibTeX RDF
25	Martin Böhm 0001, Pavel Veselý 0001	Online Chromatic Number is PSPACE-Complete.	CoRR	2016	DBLP BibTeX RDF
25	Massimo Cairo, Romeo Rizzi	Dynamic Controllability of Conditional Simple Temporal Networks is PSPACE-complete.	CoRR	2016	DBLP BibTeX RDF