Stem pspace$ (all stems)

34 papers:

FoSSaCS-2015-HoO #problem

The Cyclic-Routing UAV Problem is PSPACE-Complete (HMH, JO), pp. 328–342.

LICS-2015-BlondinFGHM #2d #reachability

Reachability in Two-Dimensional Vector Addition Systems with States Is PSPACE-Complete (MB, AF, SG, CH, PM), pp. 32–43.

ICALP-v2-2014-Jez #unification

Context Unification is in PSPACE (AJ), pp. 244–255.

LICS-CSL-2014-HeijltjesH #equivalence #proving

No proof nets for MLL with units: proof equivalence in MLL is PSPACE-complete (WH, RH), p. 10.

ICALP-v1-2013-Grier #finite #game studies

Deciding the Winner of an Arbitrary Finite Poset Game Is PSPACE-Complete (DG), pp. 497–503.

ICALP-v2-2013-FearnleyJ #automaton #reachability

Reachability in Two-Clock Timed Automata Is PSPACE-Complete (JF, MJ), pp. 212–223.

GRAPHITE-2013-Majster-CederbaumS #architecture #constraints #operating system #reachability

Reachability in Cooperating Systems with Architectural Constraints is PSPACE-Complete (MEMC, NS), pp. 1–11.

CSL-2013-Oitavem #nondeterminism #recursion

From determinism, non-determinism and alternation to recursion schemes for P, NP and Pspace (Invited Talk) (IO), pp. 24–27.

STOC-2010-JainJUW

QIP = PSPACE (RJ, ZJ, SU, JW), pp. 573–582.

POPL-2008-GaboardiMR #logic

A logical account of pspace (MG, JYM, SRDR), pp. 121–131.

LATA-2007-BaaderHP #automaton #exclamation #logic

SI! Automata Can Show PSPACE Results for Description Logics (FB, JH, RP), pp. 67–78.

CSL-2007-HertelU #game studies

Game Characterizations and the PSPACE-Completeness of Tree Resolution Space (AH, AU), pp. 527–541.

IJCAR-2006-DemriL #logic

Presburger Modal Logic Is PSPACE-Complete (SD, DL), pp. 541–556.

LICS-2006-PanV #parametricity

Fixed-Parameter Hierarchies inside PSPACE (GP, MYV), pp. 27–36.

LICS-2006-SchroderP #bound #logic

PSPACE Bounds for Rank-1 Modal Logics (LS, DP), pp. 231–242.

ICALP-2004-Skelley #quantifier #reasoning #source code

Propositional PSPACE Reasoning with Boolean Programs Versus Quantified Boolean Formulas (AS), pp. 1163–1175.

CSL-2004-Richerby #logic

Logical Characterizations of PSPACE (DR), pp. 370–384.

CSL-2004-Skelley #bound #higher-order

A Third-Order Bounded Arithmetic Theory for PSPACE (AS), pp. 340–354.

LICS-2003-Jancar #parallel #process #similarity

Strong Bisimilarity on Basic Parallel Processes is PSPACE-complete (PJ), p. 218–?.

ICALP-2002-Srba #algebra #process #similarity

Strong Bisimilarity and Regularity of Basic Process Algebra Is PSPACE-Hard (JS), pp. 716–727.

CSL-2001-Schmidt-Schauss #unification

Stratified Context Unification Is in PSPACE (MSS), pp. 498–512.

STOC-2000-Gutierrez #equation #satisfiability

Satisfiability of equations in free groups is in PSPACE (CG), pp. 21–27.

LICS-1999-NiehrenMT #constraints #set

Entailment of Atomic Set Constraints is PSPACE-Complete (JN, MM, JMT), pp. 285–294.

CSL-1996-Dziembowski #bound #fixpoint #query

Bounded-Variable Fixpoint Queries are PSPACE-complete (SD), pp. 89–105.

STOC-1994-AroraRV #polynomial #simulation

Simulating quadratic dynamical systems is PSPACE-complete (preliminary version) (SA, YR, UVV), pp. 459–467.

STOC-1994-MaratheHSR #approximate #problem #specification

Approximation schemes for PSPACE-complete problems for succinct specifications (preliminary version) (MVM, HBHI, RES, VR), pp. 468–477.

ICALP-1994-BirgetMMW #algorithm #problem

PSPACE-Completeness of Certain Algorithmic Problems on the Subgroups of Free Groups (JCB, SWM, JCM, PW), pp. 274–285.

STOC-1993-CondonFLS #algorithm #approximate

Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions (AC, JF, CL, PWS), pp. 305–314.

ICALP-1993-MaratheHR #approximate #complexity #problem #specification

The Complexity of Approximating PSPACE-Complete Problems for Hierarchical Specifications (Extended Abstract) (MVM, HBHI, SSR), pp. 76–87.

STOC-1988-Canny #algebra #geometry

Some Algebraic and Geometric Computations in PSPACE (JFC), pp. 460–467.

CADE-1988-AabyN #logic

Propositional Temporal Interval Logic is PSPACE Complete (AAA, KTN), pp. 218–237.

STOC-1986-Cai #polynomial #probability #random

With Probability One, A Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy (JyC), pp. 21–29.

STOC-1981-UkkonenS #lalr #testing

LALR(k) Testing is PSPACE-Complete (EU, ESS), pp. 202–206.

ICALP-1978-Lingas #game studies #problem

A PSPACE Complete Problem Related to a Pebble Game (AL), pp. 300–321.