Search results for "PSPACE-complete"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
2	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
2	Kyle W. Burke, Shang-Hua Teng	A PSPACE-complete Sperner Triangle Game.	WINE	2007	DBLP DOI BibTeX RDF
2	Krishnendu Chatterjee	Stochastic Müller Games are PSPACE-Complete.	FSTTCS	2007	DBLP DOI BibTeX RDF
2	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
2	Stéphane Demri, Denis Lugiez	Presburger Modal Logic Is PSPACE-Complete.	IJCAR	2006	DBLP DOI BibTeX RDF
2	Volker Diekert, Claudio Gutiérrez, 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
2	Keijo Heljanko	Model Checking with Finite Complete Prefixes Is PSPACE-Complete.	CONCUR	2000	DBLP DOI BibTeX RDF
2	Marcel Crâsmaru, John Tromp	Ladders Are PSPACE-Complete.	Computers and Games	2000	DBLP DOI BibTeX RDF
2	Ke Yang	Integer Circuit Evaluation is PSPACE-Complete. (PDF / PS)	IEEE Conference on Computational Complexity	2000	DBLP DOI BibTeX RDF	Integer Circuit, Chinese Remainder Theorem, PSPACE
2	Marcus Schaefer	Deciding the K-Dimension is PSPACE-Complete. (PDF / PS)	IEEE Conference on Computational Complexity	2000	DBLP DOI BibTeX RDF	computational complexity, learning theory, PSPACE
2	Joachim Niehren, Martin Müller, Jean-Marc Talbot	Entailment of Atomic Set Constraints is PSPACE-Complete.	LICS	1999	DBLP DOI BibTeX RDF
2	Stefan Dziembowski	Bounded-Variable Fixpoint Queries are PSPACE-complete.	CSL	1996	DBLP DOI BibTeX RDF
2	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
2	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
1	Michael Lampis, Valia Mitsou, Karolina Soltys	Scrabble is PSPACE-Complete	CoRR	2012	DBLP BibTeX RDF
1	Giovanni Viglietta	Partial Searchlight Scheduling is Strongly PSPACE-complete	CoRR	2012	DBLP BibTeX RDF
1	Giovanni Viglietta	Lemmings is PSPACE-complete	CoRR	2012	DBLP BibTeX RDF
1	Matthew S. Bauer	A PSPACE-Complete First Order Fragment of Computability Logic	CoRR	2012	DBLP BibTeX RDF
1	Kyle W. Burke, Olivia George	A PSPACE-complete Graph Nim	CoRR	2011	DBLP BibTeX RDF
1	Christer Bäckström, Peter Jonsson	All PSPACE-Complete Planning Problems Are Equal but Some Are More Equal than Others.	SOCS	2011	DBLP BibTeX RDF
1	Félix Bou, Marco Cerami, Francesc Esteva	Finite-Valued Lukasiewicz Modal Logic Is PSPACE-Complete.	IJCAI	2011	DBLP BibTeX RDF
1	Elena V. Pribavkina, Emanuele Rodaro	Recognizing Synchronizing Automata with Finitely Many Minimal Synchronizing Words is PSPACE-Complete.	CiE	2011	DBLP DOI BibTeX RDF
1	Wouter Gelade, Frank Neven	Optimizing the Region Algebra is PSPACE-complete.	Inf. Process. Lett.	2010	DBLP DOI BibTeX RDF
1	Mila E. Majster-Cederbaum, Nils Semmelrock	Reachability in Tree-Like Component Systems is PSPACE-Complete.	Electr. Notes Theor. Comput. Sci.	2010	DBLP DOI BibTeX RDF
1	Stanislav Böhm, Stefan Göller, Petr Jancar	Bisimilarity of One-Counter Processes Is PSPACE-Complete.	CONCUR	2010	DBLP DOI BibTeX RDF
1	Wim Martens, Matthias Niewerth, Thomas Schwentick	Schema design for XML repositories: complexity and tractability.	PODS	2010	DBLP DOI BibTeX RDF	language primality, complexity, xml, xml schemas
1	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
1	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
1	Ami Hauptman, Achiya Elyasaf, Moshe Sipper, Assaf Karmon	GP-rush: using genetic programming to evolve solvers for the rush hour puzzle.	GECCO	2009	DBLP DOI BibTeX RDF	rush-hour puzzle, genetic programming, heuristics, single-agent search
1	Alin Deutsch, Richard Hull, Fabio Patrizi, Victor Vianu	Automatic verification of data-centric business processes.	ICDT	2009	DBLP DOI BibTeX RDF
1	Christian Fritz, Richard Hull, Jianwen Su	Automatic construction of simple artifact-based business processes.	ICDT	2009	DBLP DOI BibTeX RDF
1	Jorge Pérez, Marcelo Arenas, Claudio Gutierrez	Semantics and complexity of SPARQL.	ACM Trans. Database Syst.	2009	DBLP DOI BibTeX RDF	semantic Web, Complexity, query language, RDF, SPARQL
1	Florent R. Madelaine, Barnaby Martin	The Complexity of Positive First-order Logic without Equality.	LICS	2009	DBLP DOI BibTeX RDF
1	Franck Cassez, Jérémy Dubreil, Hervé Marchand	Dynamic Observers for the Synthesis of Opaque Systems.	ATVA	2009	DBLP DOI BibTeX RDF
1	Rajeev Alur, Pavol Cerný, Scott Weinstein	Algorithmic Analysis of Array-Accessing Programs.	CSL	2009	DBLP DOI BibTeX RDF
1	Angelo Montanari, Gabriele Puppis, Pietro Sala	A Decidable Spatial Logic with Cone-Shaped Cardinal Directions.	CSL	2009	DBLP DOI BibTeX RDF
1	Janusz A. Brzozowski, Elyot Grant, Jeffrey Shallit	Closures in Formal Languages and Kuratowski's Theorem.	Developments in Language Theory	2009	DBLP DOI BibTeX RDF
1	Alessandro Artale, Roman Kontchakov, Vladislav Ryzhikov, Michael Zakharyaschev	DL-Lite with Temporalised Concepts, Rigid Axioms and Roles.	FroCos	2009	DBLP DOI BibTeX RDF
1	Andreas Bauer 0002, Rajeev Goré, Alwen Tiu	A First-Order Policy Language for History-Based Transaction Monitoring.	ICTAC	2009	DBLP DOI BibTeX RDF
1	Carlos Areces, Diego Figueira, Daniel Gorín, Sergio Mera	Tableaux and Model Checking for Memory Logics.	TABLEAUX	2009	DBLP DOI BibTeX RDF
1	George Metcalfe, Nicola Olivetti	Proof Systems for a Gödel Modal Logic.	TABLEAUX	2009	DBLP DOI BibTeX RDF
1	Panagiotis Manolios, Aaron Turon	All-Termination(T).	TACAS	2009	DBLP DOI BibTeX RDF
1	Takehiro Ito, Marcin Kaminski, Erik D. Demaine	Reconfiguration of List Edge-Colorings in a Graph.	WADS	2009	DBLP DOI BibTeX RDF
1	Kyle W. Burke, Shang-Hua Teng	Atropos: A PSPACE-Complete Sperner Triangle Game.	Internet Mathematics	2008	DBLP DOI BibTeX RDF
1	Mila E. Majster-Cederbaum, Christoph Minnameier	Everything Is PSPACE-Complete in Interaction Systems.	ICTAC	2008	DBLP DOI BibTeX RDF
1	Alex Fabrikant, Christos H. Papadimitriou	The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond.	SODA	2008	DBLP DOI BibTeX RDF
1	Brendan Juba, Madhu Sudan	Universal semantic communication I.	STOC	2008	DBLP DOI BibTeX RDF	computational complexity, interaction, linguistics
1	Alexander Skopalik, Berthold Vöcking	Inapproximability of pure nash equilibria.	STOC	2008	DBLP DOI BibTeX RDF	approximation, local search, congestion games
1	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
1	Christel Baier, Nathalie Bertrand, Patricia Bouyer, Thomas Brihaye, Marcus Größer	Almost-Sure Model Checking of Infinite Paths in One-Clock Timed Automata.	LICS	2008	DBLP DOI BibTeX RDF
1	Somesh Jha, Ninghui Li, Mahesh V. Tripunitara, Qihua Wang, William H. Winsborough	Towards Formal Verification of Role-Based Access Control Policies.	IEEE Trans. Dependable Sec. Comput.	2008	DBLP DOI BibTeX RDF
1	Krishnendu Chatterjee, Luca de Alfaro, Rupak Majumdar	The Complexity of Coverage.	APLAS	2008	DBLP DOI BibTeX RDF
1	Matthias Baaz, Richard Zach	Effective Finite-Valued Approximations of General Propositional Logics.	Pillars of Computer Science	2008	DBLP DOI BibTeX RDF
1	Thierry Boy de la Tour, Mnacho Echenim, Paliath Narendran	Unification and Matching Modulo Leaf-Permutative Equational Presentations.	IJCAR	2008	DBLP DOI BibTeX RDF
1	Juraj Hromkovic, Georg Schnitger	On the Hardness of Determining Small NFA's and of Proving Lower Bounds on Their Sizes.	Developments in Language Theory	2008	DBLP DOI BibTeX RDF
1	Victor L. Selivanov, Klaus W. Wagner	Complexity of Topological Properties of Regular omega-Languages.	Developments in Language Theory	2008	DBLP DOI BibTeX RDF
1	Marcin Jurdzinski, Ashutosh Trivedi	Concavely-Priced Timed Automata.	FORMATS	2008	DBLP DOI BibTeX RDF
1	Alexander Rabinovich	Complexity of Metric Temporal Logics with Counting and the Pnueli Modalities.	FORMATS	2008	DBLP DOI BibTeX RDF
1	Stéphane Demri, Ranko Lazic, Arnaud Sangnier	Model Checking Freeze LTL over One-Counter Automata.	FoSSaCS	2008	DBLP DOI BibTeX RDF
1	Fedor V. Fomin, Petr A. Golovach, Alexander Hall, Matús Mihalák, Elias Vicari, Peter Widmayer	How to Guard a Graph?.	ISAAC	2008	DBLP DOI BibTeX RDF
1	Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, Yushi Uno	On the Complexity of Reconfiguration Problems.	ISAAC	2008	DBLP DOI BibTeX RDF
1	Aniello Murano, Margherita Napoli, Mimmo Parente	Program Complexity in Hierarchical Module Checking.	LPAR	2008	DBLP DOI BibTeX RDF
1	Sarmad Abbasi, Numan Sheikh	Question/Answer Games on Towers and Pyramids.	MFCS	2008	DBLP DOI BibTeX RDF
1	Helmut Seidl, Andrea Flexeder, Michael Petter	Analysing All Polynomial Equations in .	SAS	2008	DBLP DOI BibTeX RDF
1	Blaise Genest, Anca Muscholl	Pattern Matching and Membership for Hierarchical Message Sequence Charts.	Theory Comput. Syst.	2008	DBLP DOI BibTeX RDF	Complexity, MSC, Hierarchical specifications
1	Aduri Pavan, Fengming Wang	Robustness of PSPACE-complete sets.	Inf. Process. Lett.	2007	DBLP DOI BibTeX RDF
1	Philipp Hertel, Toniann Pitassi	Black-White Pebbling is PSPACE-Complete.	Electronic Colloquium on Computational Complexity (ECCC)	2007	DBLP BibTeX RDF
1	Matthew Delacorte	Graph Isomorphism is PSPACE-complete	CoRR	2007	DBLP BibTeX RDF
1	Nobutaka Suzuki	An edit operation-based approach to the inclusion problem for DTDs.	SAC	2007	DBLP DOI BibTeX RDF	inclusion problem, XML, regular expression, DTD
1	Thomas Ågotnes, Natasha Alechina	Full and relative awareness: a decidable logic for reasoning about knowledge of unawareness.	TARK	2007	DBLP DOI BibTeX RDF
1	Max I. Kanovich, Paul Rowe, Andre Scedrov	Collaborative Planning With Privacy.	CSF	2007	DBLP DOI BibTeX RDF
1	Sylvain Hallé, Roger Villemaire, Omar Cherkaoui, Boubker Ghandour	Model Checking Data-Aware Workflow Properties with CTL-FO+.	EDOC	2007	DBLP DOI BibTeX RDF
1	Philipp Hertel, Toniann Pitassi	Exponential Time/Space Speedups for Resolution and the PSPACE-completeness of Black-White Pebbling.	FOCS	2007	DBLP DOI BibTeX RDF
1	Gösta Grahne, Alex Thomo	Boundedness of Regular Path Queries in Data Integration Systems.	IDEAS	2007	DBLP DOI BibTeX RDF
1	Manuel Bodirsky, Hubie Chen	Quantified Equality Constraints.	LICS	2007	DBLP DOI BibTeX RDF
1	Stéphane Demri, Régis Gascon	The Effects of Bounding Syntactic Resources on Presburger LTL.	TIME	2007	DBLP DOI BibTeX RDF
1	Anuj Dawar	Model-Checking First-Order Logic: Automata and Locality.	CSL	2007	DBLP DOI BibTeX RDF
1	Hans-Georg Breunig	The Complexity of Membership Problems for Circuits over Sets of Positive Numbers.	FCT	2007	DBLP DOI BibTeX RDF	Computational complexity, Combinational circuits, Arithmetic circuits
1	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
1	Patricia Bouyer, Kim Guldstrand Larsen, Nicolas Markey	Model-Checking One-Clock Priced Timed Automata.	FoSSaCS	2007	DBLP DOI BibTeX RDF
1	Christel Baier, Nathalie Bertrand, Patricia Bouyer, Thomas Brihaye, Marcus Größer	Probabilistic and Topological Semantics for Timed Automata.	FSTTCS	2007	DBLP DOI BibTeX RDF
1	Matthias Schmalz, Hagen Völzer, Daniele Varacca	Model Checking Almost All Paths Can Be Less Expensive Than Checking All Paths.	FSTTCS	2007	DBLP DOI BibTeX RDF
1	Laura Bozzelli, Salvatore La Torre	Decision Problems for Lower/Upper Bound Parametric Timed Automata.	ICALP	2007	DBLP DOI BibTeX RDF
1	Salvatore La Torre, Gennaro Parlato	On the Complexity of LtlModel-Checking of Recursive State Machines.	ICALP	2007	DBLP DOI BibTeX RDF
1	Michel de Rougemont, Adrien Vieilleribière	Approximate Data Exchange.	ICDT	2007	DBLP DOI BibTeX RDF
1	Stéphane Demri, Alexander Rabinovich	The Complexity of Temporal Logic with Until and Since over Ordinals.	LPAR	2007	DBLP DOI BibTeX RDF
1	Rajeev Alur, Pavol Cerný, Swarat Chaudhuri	Model Checking on Trees with Path Equivalences.	TACAS	2007	DBLP DOI BibTeX RDF
1	Jin Yi, Wenhui Zhang	Enhancing Simulation for Checking Language Containment.	TAMC	2007	DBLP DOI BibTeX RDF
1	Pierre McKenzie, Klaus W. Wagner	The Complexity of Membership Problems for Circuits Over Sets of Natural Numbers.	Computational Complexity	2007	DBLP DOI BibTeX RDF	Subject classification. 68Q25, 68Q15, 03D15
1	Luca Trevisan, Salil P. Vadhan	Pseudorandomness and Average-Case Complexity Via Uniform Reductions.	Computational Complexity	2007	DBLP DOI BibTeX RDF	Subject classification, 68Q10
1	Patricia Bouyer, Thomas Brihaye, Véronique Bruyère, Jean-François Raskin	On the optimal reachability problem of weighted timed automata.	Formal Methods in System Design	2007	DBLP DOI BibTeX RDF	Weighted timed automaton, Cost-optimal reachability problem
1	Sven Grothklags, Ulf Lorenz	Stochastic Airline Fleet Assignment is PSPACE-complete.	Electronic Notes in Discrete Mathematics	2006	DBLP DOI BibTeX RDF
1	Wiebe van der Hoek, Alessio Lomuscio, Michael Wooldridge	On the complexity of practical ATL model checking.	AAMAS	2006	DBLP DOI BibTeX RDF	verification, complexity, cooperation, logic
1	Guizhen Yang, Michael Kifer, Vinay K. Chaudhri	Efficiently ordering subgoals with access constraints.	PODS	2006	DBLP DOI BibTeX RDF	binding pattern, nonrecursive datalog, query, executability
1	Sachio Teramoto, Erik D. Demaine, Ryuhei Uehara	Voronoi game on graphs and its complexity.	CIG	2006	DBLP DOI BibTeX RDF
1	Amit Sasturkar, Ping Yang, Scott D. Stoller, C. R. Ramakrishnan	Policy Analysis for Administrative Role Based Access Control.	CSFW	2006	DBLP DOI BibTeX RDF
1	Eldar Fischer, Frédéric Magniez, Michel de Rougemont	Approximate Satisfiability and Equivalence.	LICS	2006	DBLP DOI BibTeX RDF
1	Guoqiang Pan, Moshe Y. Vardi	Fixed-Parameter Hierarchies inside PSPACE.	LICS	2006	DBLP DOI BibTeX RDF
1	Houda Bel Mokadem, Béatrice Bérard, Patricia Bouyer, François Laroussinie	Timed Temporal Logics for Abstracting Transient States.	ATVA	2006	DBLP DOI BibTeX RDF
1	Doron Bustan, John Havlicek	Some Complexity Results for SystemVerilog Assertions.	CAV	2006	DBLP DOI BibTeX RDF