Search results for "Pspace"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
18	Rahul Jain 0001, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous	QIP = PSPACE.	Commun. ACM	2010	DBLP DOI BibTeX RDF
18	Philipp Hertel, Toniann Pitassi	The PSPACE-Completeness of Black-White Pebbling.	SIAM J. Comput.	2010	DBLP DOI BibTeX RDF
18	Stanislav Böhm, Stefan Göller, Petr Jancar	Bisimilarity of One-Counter Processes Is PSPACE-Complete.	CONCUR	2010	DBLP DOI BibTeX RDF
18	Alexander Rabinovich	Temporal Logics over Linear Time Domains Are in PSPACE.	RP	2010	DBLP DOI BibTeX RDF
18	Mila E. Majster-Cederbaum, Nils Semmelrock	Reachability in Tree-Like Component Systems is PSPACE-Complete.	FACS@FMWeek	2009	DBLP DOI BibTeX RDF
18	Paul S. Bonsma, Luis Cereceda	Finding Paths between graph colourings: PSPACE-completeness and superpolynomial distances.	Theor. Comput. Sci.	2009	DBLP DOI BibTeX RDF
18	Simone Bova, Franco Montagna	The consequence relation in the logic of commutative GBL-algebras is PSPACE-complete.	Theor. Comput. Sci.	2009	DBLP DOI BibTeX RDF
18	Rahul Jain 0001, Sarvagya Upadhyay, John Watrous	Two-message quantum interactive proofs are in PSPACE	CoRR	2009	DBLP BibTeX RDF
18	Rahul Jain 0001, Sarvagya Upadhyay, John Watrous	Two-Message Quantum Interactive Proofs Are in PSPACE.	FOCS	2009	DBLP DOI BibTeX RDF	Quantum interactive proof systems, matrix multiplicative weights update method, quantum complexity
18	Kyle W. Burke, Shang-Hua Teng	Atropos: A PSPACE-Complete Sperner Triangle Game.	Internet Math.	2008	DBLP DOI BibTeX RDF
18	Yasuhiko Takenaga, Shigeru Arai	PSPACE-completeness of an escape problem.	Inf. Process. Lett.	2008	DBLP DOI BibTeX RDF
18	Isabel Oitavem	Characterizing PSPACE with pointers.	Math. Log. Q.	2008	DBLP DOI BibTeX RDF
18	Bernd Borchert	Formal Language Characterizations of P, NP, and PSPACE.	J. Autom. Lang. Comb.	2008	DBLP DOI BibTeX RDF
18	Pawel Wocjan, Dominik Janzing, Thomas Decker 0002	Measuring 4-local qubit observables could probabilistically solve PSPACE.	Quantum Inf. Comput.	2008	DBLP DOI BibTeX RDF
18	Benedek Nagy, Sándor Vályi	Interval-valued computations and their connection with PSPACE.	Theor. Comput. Sci.	2008	DBLP DOI BibTeX RDF
18	Lutz Schröder, Dirk Pattinson	The craft of model making: PSPACE bounds for non-iterative modal logics	CoRR	2008	DBLP BibTeX RDF
18	Dariusz Dereniowski	Phutball is PSPACE-hard	CoRR	2008	DBLP BibTeX RDF
18	Franz Baader, Jan Hladik, Rafael Peñaloza	Automata can show PSpace results for description logics.	Inf. Comput.	2008	DBLP DOI BibTeX RDF
18	Mila E. Majster-Cederbaum, Christoph Minnameier	Everything Is PSPACE-Complete in Interaction Systems.	ICTAC	2008	DBLP DOI BibTeX RDF
18	Ilya Shapirovsky	PSPACE-decidability of Japaridze's polymodal logic.	Advances in Modal Logic	2008	DBLP BibTeX RDF
18	Paul Gastin, Dietrich Kuske	Uniform Satisfiability in PSPACE for Local Temporal Logics Over Mazurkiewicz Traces.	Fundam. Informaticae	2007	DBLP BibTeX RDF
18	Aduri Pavan, Fengming Wang	Robustness of PSPACE-complete sets.	Inf. Process. Lett.	2007	DBLP DOI BibTeX RDF
18	Petr Sosík, Alfonso Rodríguez-Patón	Membrane computing and complexity theory: A characterization of PSPACE.	J. Comput. Syst. Sci.	2007	DBLP DOI BibTeX RDF
18	Mihaly Mezei, Ming-Ming Zhou	Pspace: a program that assesses protein space.	Source Code Biol. Medicine	2007	DBLP DOI BibTeX RDF
18	Philipp Hertel, Toniann Pitassi	Black-White Pebbling is PSPACE-Complete.	Electron. Colloquium Comput. Complex.	2007	DBLP BibTeX RDF
18	Lutz Schröder, Dirk Pattinson	PSPACE Bounds for Rank-1 Modal Logics	CoRR	2007	DBLP BibTeX RDF
18	Matthew Delacorte	Graph Isomorphism is PSPACE-complete	CoRR	2007	DBLP BibTeX RDF
18	Joseph Y. Halpern, Leandro Chaves Rêgo	Characterizing the NP-PSPACE Gap in the Satisfiability Problem for Modal Logic.	J. Log. Comput.	2007	DBLP DOI BibTeX RDF
18	Carsten Lutz, Dirk Walther 0002, Frank Wolter	Quantitative temporal logics over the reals: PSpace and below.	Inf. Comput.	2007	DBLP DOI BibTeX RDF
18	Franz Baader, Jan Hladik, Rafael Peñaloza	SI! Automata Can Show PSPACE Results for Description Logics.	LATA	2007	DBLP BibTeX RDF
18	Joost Winter	Is P = PSPACE for Infinite Time Turing Machines?	ILC	2007	DBLP DOI BibTeX RDF
18	Franz Baader, Jan Hladik, Rafael Peñaloza	Blocking Automata for PSPACE DLs.	Description Logics	2007	DBLP BibTeX RDF
18	Joseph Y. Halpern, Leandro Chaves Rêgo	Characterizing the NP-PSPACE Gap in the Satisfiability Problem for Modal Logic.	IJCAI	2007	DBLP BibTeX RDF
18	Sven Grothklags, Ulf Lorenz	Stochastic Airline Fleet Assignment is PSPACE-complete.	Electron. Notes Discret. Math.	2006	DBLP DOI BibTeX RDF
18	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
18	Joseph Y. Halpern, Leandro Chaves Rêgo	Characterizing the NP-PSPACE Gap in the Satisfiability Problem for Modal Logic	CoRR	2006	DBLP BibTeX RDF
18	Jan Hladik, Rafael Peñaloza	PSPACE Automata for Description Logics.	Description Logics	2006	DBLP BibTeX RDF
18	Alan Skelley	Theories and proof systems for PSPACE and the EXP-time hierarchy.		2006	RDF
18	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
18	Scott Aaronson	QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols	Electron. Colloquium Comput. Complex.	2005	DBLP BibTeX RDF
18	Scott Aaronson	QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols	CoRR	2005	DBLP BibTeX RDF
18	Robert A. Hearn	Amazons is PSPACE-complete	CoRR	2005	DBLP BibTeX RDF
18	Paolo Liberatore	Complexity Issues in Finding Succinct Solutions of PSPACE-Complete Problems	CoRR	2005	DBLP BibTeX RDF
18	Volker Diekert, Claudio Gutierrez 0001, Christian Hagenah	The existential theory of equations with rational constraints in free groups is PSPACE-complete.	Inf. Comput.	2005	DBLP DOI BibTeX RDF
18	Timothy Furtak, Masashi Kiyomi, Takeaki Uno, Michael Buro	Generalized Amazons is PSPACE-Complete.	IJCAI	2005	DBLP BibTeX RDF
18	Stephen A. Fenner, Stuart A. Kurtz, James S. Royer	Every polynomial-time 1-degree collapses if and only if P = PSPACE.	J. Symb. Log.	2004	DBLP DOI BibTeX RDF
18	Ilya Shapirovsky	On PSPACE-decidability in Transitive Modal Logic.	Advances in Modal Logic	2004	DBLP BibTeX RDF
18	Artiom Alhazov, Carlos Martín-Vide, Linqiang Pan	Solving a PSPACE-Complete Problem by Recognizing P Systems with Restricted Active Membranes.	Fundam. Informaticae	2003	DBLP BibTeX RDF
18	Kurt Rohloff, Tae-Sic Yoo, Stéphane Lafortune	Deciding co-observability is PSPACE-complete.	IEEE Trans. Autom. Control.	2003	DBLP DOI BibTeX RDF
18	John Watrous	PSPACE has constant-round quantum interactive proof systems.	Theor. Comput. Sci.	2003	DBLP DOI BibTeX RDF
18	Philippe Moser	RP is Small in SUBEXP else ZPP equals PSPACE and NP equals EXP	Electron. Colloquium Comput. Complex.	2003	DBLP BibTeX RDF
18	Olivier Powell	PSPACE contains almost complete problems	Electron. Colloquium Comput. Complex.	2003	DBLP BibTeX RDF
18	Evgeny Dantsin, Alexander Wolpert	A Robust Dna Computation Model That Captures Pspace.	Int. J. Found. Comput. Sci.	2003	DBLP DOI BibTeX RDF
18	Paul Gastin, Dietrich Kuske	Satisfiability and Model Checking for MSO-definable Temporal Logics are in PSPACE.	CONCUR	2003	DBLP DOI BibTeX RDF
18	Yevgeny Kazakov, Hans de Nivelle	Subsumption of Concepts in FL0y for (Cyclic) Terminologies with Respect to Descriptive Semantics is PSPACE-complete.	Description Logics	2003	DBLP BibTeX RDF
18	Wolfgang Slany	Endgame problems of Sim-like graph Ramsey avoidance games are PSPACE-complete.	Theor. Comput. Sci.	2002	DBLP DOI BibTeX RDF
18	Gary William Flake, Eric B. Baum	Rush Hour is PSPACE-complete, or "Why you should generously tip parking lot attendants".	Theor. Comput. Sci.	2002	DBLP DOI BibTeX RDF
18	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
18	Carsten Lutz	PSpace Reasoning with the Description Logic ALCF(D).	Log. J. IGPL	2002	DBLP DOI BibTeX RDF
18	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
18	Alexander V. Chagrov, Mikhail N. Rybakov	How Many Variables Does One Need to Prove PSPACE-hardness of Modal Logics.	Advances in Modal Logic	2002	DBLP BibTeX RDF
18	Erik D. Demaine, Robert A. Hearn, Michael Hoffmann 0001	Push-2-f is pspace-complete.	CCCG	2002	DBLP BibTeX RDF
18	Ke Yang 0005	Integer Circuit Evaluation Is PSPACE-Complete.	J. Comput. Syst. Sci.	2001	DBLP DOI BibTeX RDF
18	Volker Diekert, Claudio Gutierrez 0001, Christian Hagenah	The Existential Theory of Equations with Rational Constraints in Free Groups is PSPACE-Complete	CoRR	2001	DBLP BibTeX RDF
18	Stephan Tobies	PSPACE Reasoning for Graded Modal Logics.	J. Log. Comput.	2001	DBLP DOI BibTeX RDF
18	Manfred Schmidt-Schauß	Stratified Context Unification Is in PSPACE.	CSL	2001	DBLP DOI BibTeX RDF
18	Stéphane Demri	The Nondeterministic Information Logic NIL is PSPACE-complete.	Fundam. Informaticae	2000	DBLP DOI BibTeX RDF
18	Jean-Camille Birget, Stuart W. Margolis, John C. Meakin, Pascal Weil	PSPACE-complete problems for subgroups of free groups and inverse finite automata.	Theor. Comput. Sci.	2000	DBLP DOI BibTeX RDF
18	Ke Yang	Integer Circuit Evaluation is PSPACE-complete	Electron. Colloquium Comput. Complex.	2000	DBLP BibTeX RDF
18	Stephan Tobies	PSPACE Reasoning for Graded Modal Logics	CoRR	2000	DBLP BibTeX RDF
18	Ron van der Meyden	Predicate Boundedness of Linear Monadic Datalog is in PSPACE.	Int. J. Found. Comput. Sci.	2000	DBLP DOI BibTeX RDF
18	Stéphane Demri	Modal Logics with Weak Forms of Recursion: PSPACE Specimens.	Advances in Modal Logic	2000	DBLP DOI BibTeX RDF
18	Claudio Gutierrez 0001	Satisfiability of equations in free groups is in PSPACE.	STOC	2000	DBLP DOI BibTeX RDF
18	Peter Jonsson	Strong bounds on the approximability of two Pspace-hard problems in propositional planning.	Ann. Math. Artif. Intell.	1999	DBLP DOI BibTeX RDF
18	Guy Perrier	A PSPACE-complete Fragment of Second-order Linear Logic.	Theor. Comput. Sci.	1999	DBLP DOI BibTeX RDF
18	John Watrous	PSPACE has 2-round quantum interactive proof systems	CoRR	1999	DBLP BibTeX RDF
18	Madhav V. Marathe, Harry B. Hunt III, Richard Edwin Stearns, Venkatesh Radhakrishnan	Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems	CoRR	1998	DBLP BibTeX RDF
18	Harry B. Hunt III, Madhav V. Marathe, Venkatesh Radhakrishnan, S. S. Ravi, Daniel J. Rosenkrantz, Richard Edwin Stearns	NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs.	J. Algorithms	1998	DBLP DOI BibTeX RDF
18	Madhav V. Marathe, Harry B. Hunt III, Richard Edwin Stearns, Venkatesh Radhakrishnan	Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems.	SIAM J. Comput.	1998	DBLP DOI BibTeX RDF
18	L. Bernátsky	Regular Expression Star-Freeness is PSPACE-Complete.	Acta Cybern.	1997	DBLP BibTeX RDF
18	Anne Condon, Joan Feigenbaum, Carsten Lund, Peter W. Shor	Probabilistically Checkable Debate Systems and Nonapproximability of PSPACE-Hard Functions.	Chic. J. Theor. Comput. Sci.	1995	DBLP BibTeX RDF
18	Alexander Russell, Ravi Sundaram	The Relativized Relationship Between Probabilistically Chackable Debate Systems, IP and PSPACE.	Inf. Process. Lett.	1995	DBLP DOI BibTeX RDF
18	Karl R. Abrahamson, Rodney G. Downey, Michael R. Fellows	Fixed-Parameter Tractability and Completeness IV: On Completeness for W[P] and PSPACE Analogues.	Ann. Pure Appl. Log.	1995	DBLP DOI BibTeX RDF
18	Anne Condon	Approximate solutions to problems in PSPACE.	SIGACT News	1995	DBLP DOI BibTeX RDF
18	Shigeki Iwata, Takumi Kasai	The Othello game on an n*n board is PSPACE-complete.	Theor. Comput. Sci.	1994	DBLP DOI BibTeX RDF
18	Jin-yi Cai, Anne Condon, Richard J. Lipton	PSPACE Is Provable by Two Provers in One Round.	J. Comput. Syst. Sci.	1994	DBLP DOI BibTeX RDF
18	Madhav V. Marathe, Harry B. Hunt III, S. S. Ravi	The complexity of approximating PSPACE-Complete problems for hierarchical specifications.	CoRR	1994	DBLP BibTeX RDF
18	Madhav V. Marathe, Harry B. Hunt III, S. S. Ravi	The Complexity of Approximation PSPACE-Complete Problems for Hierarchical Specifications.	Nord. J. Comput.	1994	DBLP BibTeX RDF
18	Harry B. Hunt III, Madhav V. Marathe, Venkatesh Radhakrishnan, S. S. Ravi, Daniel J. Rosenkrantz, Richard Edwin Stearns	A Unified Approach to Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs.	ESA	1994	DBLP DOI BibTeX RDF
18	Sanjeev Arora, Yuval Rabani, Umesh V. Vazirani	Simulating quadratic dynamical systems is PSPACE-complete (preliminary version).	STOC	1994	DBLP DOI BibTeX RDF
18	Madhav V. Marathe, Harry B. Hunt III, Richard Edwin Stearns, Venkatesh Radhakrishnan	Approximation schemes for PSPACE-complete problems for succinct specifications (preliminary version).	STOC	1994	DBLP DOI BibTeX RDF
18	Juris Hartmanis, Richard Chang 0001, Desh Ranjan, Pankaj Rohatgi	On IP = PSPACE and Theorems with Narrow Proofs.	Current Trends in Theoretical Computer Science	1993	DBLP DOI BibTeX RDF
18	Anne Condon, Joan Feigenbaum, Carsten Lund, Peter W. Shor	Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions.	STOC	1993	DBLP DOI BibTeX RDF
18	Osamu Watanabe 0001, Shouwen Tang	On Polynomial-Time Turing and Many-One Completeness in PSPACE.	Theor. Comput. Sci.	1992	DBLP DOI BibTeX RDF
18	Sang Cho, Dung T. Huynh	Finite-Automaton Aperiodicity is PSPACE-Complete.	Theor. Comput. Sci.	1991	DBLP DOI BibTeX RDF
18	Jin-yi Cai, Merrick L. Furst	PSPACE Survives Constant-Width Bottlenecks.	Int. J. Found. Comput. Sci.	1991	DBLP DOI BibTeX RDF
18	Jin-yi Cai, Anne Condon, Richard J. Lipton	PSPACE Is Provable By Two Provers In One Round.	SCT	1991	DBLP DOI BibTeX RDF
18	Jin-yi Cai	With Probability One, a Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy.	J. Comput. Syst. Sci.	1989	DBLP DOI BibTeX RDF
18	Stephen A. Fenner, Stuart A. Kurtz, James S. Royer	Every Polynomial-Time 1-Degree Collapses iff P=PSPACE	FOCS	1989	DBLP DOI BibTeX RDF	equivalent sets, m-reducible, Karp-reducible, polynomial-time computable function
18	Osamu Watanabe 0001, Shouwen Tang	On Polynomial Time Turing and Many-One Completeness in PSPACE.	SCT	1989	DBLP DOI BibTeX RDF