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 |
|