Search results for "PSPACE"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
86	Alan Skelley	A Third-Order Bounded Arithmetic Theory for PSPACE.	CSL	2004	DBLP DOI BibTeX RDF	quantified propositional calculus, Bounded arithmetic, PSPACE, propositional proof complexity
67	Isabel Oitavem	Implicit Characterizations of Pspace.	Proof Theory in Computer Science	2001	DBLP DOI BibTeX RDF	implicit characterizations, computational complexity, term rewriting, Pspace
58	Marcus Schaefer 0001	Deciding the K-Dimension is PSPACE-Complete.	CCC	2000	DBLP DOI BibTeX RDF	computational complexity, learning theory, PSPACE
58	Ke Yang	Integer Circuit Evaluation is PSPACE-Complete.	CCC	2000	DBLP DOI BibTeX RDF	Integer Circuit, Chinese Remainder Theorem, PSPACE
56	Robert A. Hearn, Erik D. Demaine	The Nondeterministic Constraint Logic Model of Computation: Reductions and Applications.	ICALP	2002	DBLP DOI BibTeX RDF
55	Rahul Jain 0001, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous	QIP = PSPACE.	STOC	2010	DBLP DOI BibTeX RDF	matrix multiplicative weights update method, quantum interactive proof systems, quantum computation, semidefinite programming
48	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
48	Alexander Shen	IP = PSPACE: Simplified Proof.	J. ACM	1992	DBLP DOI BibTeX RDF	interactive proofs, PSPACE
47	Serge Abiteboul, Gerd G. Hillebrand	Space Usage in Functional Query Languages.	ICDT	1995	DBLP DOI BibTeX RDF
46	Lutz Schröder, Dirk Pattinson	PSPACE Bounds for Rank-1 Modal Logics.	LICS	2006	DBLP DOI BibTeX RDF
46	Guoqiang Pan, Moshe Y. Vardi	Fixed-Parameter Hierarchies inside PSPACE.	LICS	2006	DBLP DOI BibTeX RDF
46	Stéphane Demri, Denis Lugiez	Presburger Modal Logic Is PSPACE-Complete.	IJCAR	2006	DBLP DOI BibTeX RDF
46	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
46	Petr Jancar	Strong Bisimilarity on Basic Parallel Processes is PSPACE-complete.	LICS	2003	DBLP DOI BibTeX RDF
46	Christof Löding, Philipp Rohde	Solving the Sabotage Game Is PSPACE-Hard.	MFCS	2003	DBLP DOI BibTeX RDF
46	Joachim Niehren, Martin Müller 0001, Jean-Marc Talbot	Entailment of Atomic Set Constraints is PSPACE-Complete.	LICS	1999	DBLP DOI BibTeX RDF
46	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
46	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
40	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
40	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
39	Adi Shamir	IP = PSPACE.	J. ACM	1992	DBLP DOI BibTeX RDF	IP, interactive proofs, PSPACE
39	Adi Shamir	IP=PSPACE	FOCS	1990	DBLP DOI BibTeX RDF	acceptance probability, honest provers, public coins, logarithmic workspace, two-way access, random tape, interaction, IP, randomization, polynomial time, one-way functions, zero-knowledge proofs, interactive proofs, PSPACE, polynomial space, proof verification
39	James Renegar	A Faster PSPACE Algorithm for Deciding the Existential Theory of the Reals	FOCS	1988	DBLP DOI BibTeX RDF	real polynomials, PSPACE algorithm, existential theory, atomic predicates, Boolean function, set, decision problem
39	Andrzej Lingas	A PSPACE Complete Problem Related to a Pebble Game.	ICALP	1978	DBLP DOI BibTeX RDF	dag, completeness in polynomial space, computational complexity, PSPACE, pebble game, AND/OR graph
38	Peter Niebert, Doron A. Peled	Efficient Model Checking for LTL with Partial Order Snapshots.	TACAS	2006	DBLP DOI BibTeX RDF
38	Thomas Eiter, Georg Gottlob	On the Complexity of Theory Curbing.	LPAR	2000	DBLP DOI BibTeX RDF
38	Richard Mayr	On the Complexity of Bisimulation Problems for Pushdown Automata.	IFIP TCS	2000	DBLP DOI BibTeX RDF	verification, complexity, bisimulation, Pushdown automata
38	Madhav V. Marathe, Venkatesh Radhakrishnan, Harry B. Hunt III, S. S. Ravi	Hierarchical Specified Unit Disk Graphs (Extended Abstract).	WG	1993	DBLP DOI BibTeX RDF
38	Ronald V. Book, Jack H. Lutz, Klaus W. Wagner	On Complexity Classes and Algorithmically Random Languages (Extended Abstract).	STACS	1992	DBLP DOI BibTeX RDF
37	Lutz Schröder, Dirk Pattinson	PSPACE bounds for rank-1 modal logics.	ACM Trans. Comput. Log.	2009	DBLP DOI BibTeX RDF	Shallow models, resolution, coalgebra
37	Marco Gaboardi, Jean-Yves Marion, Simona Ronchi Della Rocca	A logical account of pspace.	POPL	2008	DBLP DOI BibTeX RDF	type assignment, linear logic, implicit computational complexity, polynomial space
37	Kai Engelhardt, Peter Gammie, Ron van der Meyden	Model Checking Knowledge and Linear Time: PSPACE Cases.	LFCS	2007	DBLP DOI BibTeX RDF
37	Petr Sosík, Alfonso Rodríguez-Patón	P Systems with Active Membranes Characterize PSPACE.	DNA	2006	DBLP DOI BibTeX RDF
37	Carsten Lutz, Dirk Walther 0002, Frank Wolter	Quantitative Temporal Logics: PSPACE and Below.	TIME	2005	DBLP DOI BibTeX RDF
37	Alan Skelley	Propositional PSPACE Reasoning with Boolean Programs Versus Quantified Boolean Formulas.	ICALP	2004	DBLP DOI BibTeX RDF
37	Jirí Srba	Strong Bisimilarity and Regularity of Basic Parallel Processes Is PSPACE-Hard.	STACS	2002	DBLP DOI BibTeX RDF
37	Marcel Crâsmaru, John Tromp	Ladders Are PSPACE-Complete.	Computers and Games	2000	DBLP DOI BibTeX RDF
30	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
30	André Berger, Ralf Hoffmann, Ulf Lorenz, Sebastian Stiller	TOPSU - RDM a simulation platform for online railway delay management.	SimuTools	2008	DBLP DOI BibTeX RDF	online railway delay management, simulation, heuristics, transportation, stochastic scheduling, PSPACE, experimental algorithms, online optimization, web-based simulation
30	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
30	Mihhail Matskin, Enn Tyugu	Strategies of Structural Synthesis of Programs.	ASE	1997	DBLP DOI BibTeX RDF	structural program synthesis strategies, deductive program synthesis method, compositional programming, decidable logical calculus, PSPACE complexity, independent subtasks, iteration synthesis, regular data structures, heuristics, programming environments, structured programming, proof search, search efficiency
30	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
30	Deepak Kapur, Paliath Narendran, Hantao Zhang 0001	Complexity of Sufficient-Completeness.	FSTTCS	1986	DBLP DOI BibTeX RDF	normal forms, term rewriting systems, PSPACE, Sufficient-completeness
30	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
28	Robert S. R. Myers, Dirk Pattinson, Lutz Schröder	Coalgebraic Hybrid Logic.	FoSSaCS	2009	DBLP DOI BibTeX RDF
28	Stéphane Demri, Alexander Rabinovich	The Complexity of Temporal Logic with Until and Since over Ordinals.	LPAR	2007	DBLP DOI BibTeX RDF
28	Laura Bozzelli, Salvatore La Torre	Decision Problems for Lower/Upper Bound Parametric Timed Automata.	ICALP	2007	DBLP DOI BibTeX RDF
28	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
28	Tomasz Jurdzinski	On Complexity of Grammars Related to the Safety Problem.	ICALP (2)	2006	DBLP DOI BibTeX RDF
28	Paul Hunter, Anuj Dawar	Complexity Bounds for Regular Games.	MFCS	2005	DBLP DOI BibTeX RDF
28	Kousha Etessami, Mihalis Yannakakis	Algorithmic Verification of Recursive Probabilistic State Machines.	TACAS	2005	DBLP DOI BibTeX RDF
28	Stéphane Demri	LTL over Integer Periodicity Constraints: (Extended Abstract).	FoSSaCS	2004	DBLP DOI BibTeX RDF
28	Marcin Rychlik	On Probabilistic Quantified Satisfability Games.	MFCS	2003	DBLP DOI BibTeX RDF
28	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
28	Erez Petrank, Gábor Tardos	On the Knowledge Complexity of NP.	Comb.	2002	DBLP DOI BibTeX RDF	AMS Subject Classification (2000) Classes: 68Q15, 68Q17
28	Shin Aida, Marcel Crâsmaru, Kenneth W. Regan, Osamu Watanabe 0001	Games with a Uniqueness Property.	STACS	2002	DBLP DOI BibTeX RDF
28	Edith Hemaspaandra	The Complexity of Poor Man's Logic.	STACS	2000	DBLP DOI BibTeX RDF
28	Hing Leung	On Finite Automata with Limited Nondeterminism.	Acta Informatica	1998	DBLP DOI BibTeX RDF
28	Ronald V. Book, Heribert Vollmer, Klaus W. Wagner	On Type-2 Probabilistic Quantifiers.	ICALP	1996	DBLP DOI BibTeX RDF
28	David Lichtenstein, Michael Sipser	GO Is Polynomial-Space Hard.	J. ACM	1980	DBLP DOI BibTeX RDF
27	Philipp Hertel, Toniann Pitassi	Exponential Time/Space Speedups for Resolution and the PSPACE-completeness of Black-White Pebbling.	FOCS	2007	DBLP DOI BibTeX RDF
27	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
27	Kyle W. Burke, Shang-Hua Teng	A PSPACE-complete Sperner Triangle Game.	WINE	2007	DBLP DOI BibTeX RDF
27	Alexander Hertel, Alasdair Urquhart	Game Characterizations and the PSPACE-Completeness of Tree Resolution Space.	CSL	2007	DBLP DOI BibTeX RDF
27	Krishnendu Chatterjee	Stochastic Müller Games are PSPACE-Complete.	FSTTCS	2007	DBLP DOI BibTeX RDF
27	Scott Aaronson	QMA/qpoly \subseteq PSPACE/poly: De-Merlinizing Quantum Protocols.	CCC	2006	DBLP DOI BibTeX RDF
27	Wojciech Plandowski	Satisfiability of word equations with constants is in PSPACE.	J. ACM	2004	DBLP DOI BibTeX RDF	String unification, word equations
27	David Richerby	Logical Characterizations of PSPACE.	CSL	2004	DBLP DOI BibTeX RDF	choice operators, partial fixed points, descriptive complexity, Finite model theory
27	Jirí Srba	Strong Bisimilarity and Regularity of Basic Process Algebra Is PSPACE-Hard.	ICALP	2002	DBLP DOI BibTeX RDF
27	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
27	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
27	Keijo Heljanko	Model Checking with Finite Complete Prefixes Is PSPACE-Complete.	CONCUR	2000	DBLP DOI BibTeX RDF
27	Wojciech Plandowski	Satisfiability of Word Equations with Constants is in PSPACE.	FOCS	1999	DBLP DOI BibTeX RDF	word equations
27	John Watrous	PSPACE Has Constant-Round Quantum Interactive Proof Systems.	FOCS	1999	DBLP DOI BibTeX RDF	quantum computation, interactive proof systems
27	Stephan Tobies	A PSpace Algorithm for Graded Modal Logic.	CADE	1999	DBLP DOI BibTeX RDF
27	Stefan Dziembowski	Bounded-Variable Fixpoint Queries are PSPACE-complete.	CSL	1996	DBLP DOI BibTeX RDF
27	A. A. Aaby, K. T. Narayana	Propositional Temporal Interval Logic is PSPACE Complete.	CADE	1988	DBLP DOI BibTeX RDF
21	Martin Mundhenk, Judy Goldsmith, Christopher Lusena, Eric Allender	Complexity of finite-horizon Markov decision process problems.	J. ACM	2000	DBLP DOI BibTeX RDF	NPPP, computational complexity, Markov decision processes, NP, PL, partially observable Markov decision processes, PSPACE, succinct representations
21	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
21	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
21	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
21	John H. Reif, J. D. Tygar, Akitoshi Yoshida	The Computability and Complexity of Optical Beam Tracing	FOCS	1990	DBLP DOI BibTeX RDF	optical models, refractive surfaces, undecidable problem, PSPACE-hard problem, optical beam tracing, ray-tracing problem, reflective surfaces, incident angle, complexity, computability
21	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
21	Jin-yi Cai	Lower Bounds for Constant Depth Circuits in the Presence of Help Bits	FOCS	1989	DBLP DOI BibTeX RDF	help bit, arbitrary Boolean function, exponential lower bound, parity functions, random oracle separation, constant depth circuits, constant depth circuit, PSPACE, PH
21	Costas Courcoubetis, Mihalis Yannakakis	Verifying Temporal Properties of Finite-State Probabilistic Programs	FOCS	1988	DBLP DOI BibTeX RDF	finite-state probabilistic programs, concurrent programs, linear temporal logic, temporal properties, sequential programs, PSPACE, omega -automata
19	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
19	Kousha Etessami, Mihalis Yannakakis	Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations.	J. ACM	2009	DBLP DOI BibTeX RDF	Recursive Markov chains, monotone nonlinear systems, multi-type branching processes, Newton's method, stochastic context-free grammars
19	Vahab S. Mirrokni, Alexander Skopalik	On the complexity of nash dynamics and sink equilibria.	EC	2009	DBLP DOI BibTeX RDF	potential games, sink equilibria, nash equilibria
19	Panagiotis Manolios, Aaron Turon	All-Termination(T).	TACAS	2009	DBLP DOI BibTeX RDF
19	Yael Tauman Kalai, Ran Raz	Probabilistically Checkable Arguments.	CRYPTO	2009	DBLP DOI BibTeX RDF
19	Aduri Pavan, N. V. Vinodchandran	2-Local Random Reductions to 3-Valued Functions.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	68Q17, Subject classification. 68Q15
19	Amir M. Ben-Amram	Size-change termination with difference constraints.	ACM Trans. Program. Lang. Syst.	2008	DBLP DOI BibTeX RDF	size-change graph, size-change termination, Abstraction, program analysis, termination analysis
19	Somesh Jha, Ninghui Li, Mahesh V. Tripunitara, Qihua Wang, William H. Winsborough	Towards Formal Verification of Role-Based Access Control Policies.	IEEE Trans. Dependable Secur. Comput.	2008	DBLP DOI BibTeX RDF
19	Alex Fabrikant, Christos H. Papadimitriou	The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond.	SODA	2008	DBLP BibTeX RDF
19	Lutz Schröder, Dirk Pattinson	Shallow Models for Non-iterative Modal Logics.	KI	2008	DBLP DOI BibTeX RDF
19	Krishnendu Chatterjee, Koushik Sen, Thomas A. Henzinger	Model-Checking omega-Regular Properties of Interval Markov Chains.	FoSSaCS	2008	DBLP DOI BibTeX RDF
19	Adam Antonik, Michael Huth 0001, Kim Guldstrand Larsen, Ulrik Nyman, Andrzej Wasowski	Complexity of Decision Problems for Mixed and Modal Specifications.	FoSSaCS	2008	DBLP DOI BibTeX RDF
19	Alexander Rabinovich	Complexity of Metric Temporal Logics with Counting and the Pnueli Modalities.	FORMATS	2008	DBLP DOI BibTeX RDF
19	Daniel Meister 0001	Polynomial-Space Decidable Membership Problems for Recurrent Systems over Sets of Natural Numbers.	Theory Comput. Syst.	2007	DBLP DOI BibTeX RDF
19	Christel Baier, Tomás Brázdil, Marcus Größer, Antonín Kucera 0001	Stochastic Game Logic.	QEST	2007	DBLP DOI BibTeX RDF