Search results for "Pspace"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
9	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
9	Davide Bresolin, Valentin Goranko, Angelo Montanari, Pietro Sala	Tableau Systems for Logics of Subinterval Structures over Dense Orderings.	TABLEAUX	2007	DBLP DOI BibTeX RDF
9	Alejandro Estrella-Balderrama, Elisabeth Gassner, Michael Jünger, Merijam Percan, Marcus Schaefer 0001, Michael Schulz 0001	Simultaneous Geometric Graph Embeddings.	GD	2007	DBLP DOI BibTeX RDF
9	Thomas Schwentick, Volker Weber	Bounded-Variable Fragments of Hybrid Logics.	STACS	2007	DBLP DOI BibTeX RDF
9	Rajeev Alur, Pavol Cerný, Swarat Chaudhuri	Model Checking on Trees with Path Equivalences.	TACAS	2007	DBLP DOI BibTeX RDF
9	Michel de Rougemont, Adrien Vieilleribière	Approximate Data Exchange.	ICDT	2007	DBLP DOI BibTeX RDF
9	Eric J. Friedman, Adam Scott Landsberg	Scaling, Renormalization, and Universality in Combinatorial Games: The Geometry of Chomp.	COCOA	2007	DBLP DOI BibTeX RDF
9	Anuj Dawar	Model-Checking First-Order Logic: Automata and Locality.	CSL	2007	DBLP DOI BibTeX RDF
9	Benedikt Bollig, Dietrich Kuske, Ingmar Meinecke	Propositional Dynamic Logic for Message-Passing Systems.	FSTTCS	2007	DBLP DOI BibTeX RDF
9	Christel Baier, Nathalie Bertrand 0001, Patricia Bouyer, Thomas Brihaye, Marcus Größer	Probabilistic and Topological Semantics for Timed Automata.	FSTTCS	2007	DBLP DOI BibTeX RDF
9	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
9	Alexander A. Sherstov	Halfspace Matrices.	CCC	2007	DBLP DOI BibTeX RDF
9	Sylvain Hallé, Roger Villemaire, Omar Cherkaoui, Boubker Ghandour	Model Checking Data-Aware Workflow Properties with CTL-FO+.	EDOC	2007	DBLP DOI BibTeX RDF
9	Daniel Kirsten	A Burnside Approach to the Finite Substitution Problem.	Theory Comput. Syst.	2006	DBLP DOI BibTeX RDF
9	Martin E. Dyer, Leen Stougie	Computational complexity of stochastic programming problems.	Math. Program.	2006	DBLP DOI BibTeX RDF
9	K. Subramani 0001, C. Tauras	An approximation algorithm for state minimization in 2-MDFAs.	Formal Aspects Comput.	2006	DBLP DOI BibTeX RDF	2-MDFA, Finite state automata, State minimization
9	Jorge Pérez 0001, Marcelo Arenas, Claudio Gutierrez 0001	Semantics and Complexity of SPARQL.	ISWC	2006	DBLP DOI BibTeX RDF
9	Yung-Pin Cheng, Yu-Ru Cheng, Hong-Yi Wang	ARCATS: a scalable compositional analysis tool suite.	SAC	2006	DBLP DOI BibTeX RDF	context constraints, refactoring, compositional analysis, branching bisimulation
9	Amit Sasturkar, Ping Yang 0002, Scott D. Stoller, C. R. Ramakrishnan 0001	Policy Analysis for Administrative Role Based Access Control.	CSFW	2006	DBLP DOI BibTeX RDF
9	Eldar Fischer, Frédéric Magniez, Michel de Rougemont	Approximate Satisfiability and Equivalence.	LICS	2006	DBLP DOI BibTeX RDF
9	Kousha Etessami, Mihalis Yannakakis	Recursive Concurrent Stochastic Games.	ICALP (2)	2006	DBLP DOI BibTeX RDF
9	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
9	Olivier Serre	Parity Games Played on Transition Graphs of One-Counter Processes.	FoSSaCS	2006	DBLP DOI BibTeX RDF
9	Philipp Rohde	On the µ-Calculus Augmented with Sabotage.	FoSSaCS	2006	DBLP DOI BibTeX RDF
9	Eli Gafni	Read-Write Reductions.	ICDCN	2006	DBLP DOI BibTeX RDF
9	Michael Codish, Vitaly Lagoon, Peter Schachte, Peter J. Stuckey	Size-Change Termination Analysis in k-Bits.	ESOP	2006	DBLP DOI BibTeX RDF
9	Linh Anh Nguyen	The Data Complexity of MDatalog in Basic Modal Logics.	MFCS	2006	DBLP DOI BibTeX RDF
9	Xiaoyang Gu, Jack H. Lutz	Dimension Characterizations of Complexity Classes.	MFCS	2006	DBLP DOI BibTeX RDF
9	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
9	Sachio Teramoto, Erik D. Demaine, Ryuhei Uehara	Voronoi game on graphs and its complexity.	CIG	2006	DBLP DOI BibTeX RDF
9	Jordi Levy, Manfred Schmidt-Schauß, Mateu Villaret	Stratified Context Unification Is NP-Complete.	IJCAR	2006	DBLP DOI BibTeX RDF
9	Borzoo Bonakdarpour, Sandeep S. Kulkarni	Automated Incremental Synthesis of Timed Automata.	FMICS/PDMC	2006	DBLP DOI BibTeX RDF	Bounded liveness, Bounded response, Real-time, Formal methods, Synthesis, Transformation, Timed automata
9	Uwe Bubeck, Hans Kleine Büning	Dependency Quantified Horn Formulas: Models and Complexity.	SAT	2006	DBLP DOI BibTeX RDF
9	Hans Kleine Büning, Xishun Zhao	Minimal False Quantified Boolean Formulas.	SAT	2006	DBLP DOI BibTeX RDF
9	Roberto Sebastiani, Michele Vescovi	Encoding the Satisfiability of Modal and Description Logics into SAT: The Case Study of K(m)/ALC.	SAT	2006	DBLP DOI BibTeX RDF
9	Koushik Sen, Mahesh Viswanathan 0001, Gul Agha	Model-Checking Markov Chains in the Presence of Uncertainties.	TACAS	2006	DBLP DOI BibTeX RDF
9	Philippe Moser	Martingale Families and Dimension in P.	CiE	2006	DBLP DOI BibTeX RDF
9	Lars Kristiansen	Complexity-Theoretic Hierarchies.	CiE	2006	DBLP DOI BibTeX RDF	subrecursive classes, ?-calculi, Gödel’s T, types, Complexity theory
9	Laura Bozzelli	Complexity Results on Branching-Time Pushdown Model Checking.	VMCAI	2006	DBLP DOI BibTeX RDF
9	Daniel Sawitzki	Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms.	LATIN	2006	DBLP DOI BibTeX RDF
9	Daniel Sawitzki	The Complexity of Problems on Implicitly Represented Inputs.	SOFSEM	2006	DBLP DOI BibTeX RDF
9	Christian Dax, Martin Hofmann 0001, Martin Lange	A Proof System for the Linear Time µ-Calculus.	FSTTCS	2006	DBLP DOI BibTeX RDF
9	Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen	On the Complexity of Numerical Analysis.	CCC	2006	DBLP DOI BibTeX RDF
9	Ralf Küsters	On the decidability of cryptographic protocols with open-ended data structures.	Int. J. Inf. Sec.	2005	DBLP DOI BibTeX RDF	Complexity, Cryptographic protocols, Decidability, Transducers
9	Marco Cadoli, Thomas Eiter, Georg Gottlob	Complexity of propositional nested circumscription and nested abnormality theories.	ACM Trans. Comput. Log.	2005	DBLP DOI BibTeX RDF	Horn theories, nested abnormality theories, computational complexity, nonmonotonic reasoning, knowledge representation and reasoning, Circumscription
9	Pascal Koiran	Valiant's model and the cost of computing integers.	Comput. Complex.	2005	DBLP DOI BibTeX RDF	68Q17, Subject classification. 68Q15, 03D15
9	Yasuyuki Tsukada	Interactive and Probabilistic Proof of Mobile Code Safety.	Autom. Softw. Eng.	2005	DBLP DOI BibTeX RDF	software verification, proof-carrying code, interactive proof system
9	Michael J. Wooldridge, Paul E. Dunne	The complexity of agent design problems: Determinism and history dependence.	Ann. Math. Artif. Intell.	2005	DBLP DOI BibTeX RDF	AMS subject classification 03D15 (complexity), 68T35 (artificial intelligence)
9	Carme Àlvarez, Joaquim Gabarró, Maria J. Serna	Polynomial Space Suffices for Deciding Nash Equilibria Properties for Extensive Games with Large Trees, .	ISAAC	2005	DBLP DOI BibTeX RDF
9	Hitoshi Ohsaki, Jean-Marc Talbot, Sophie Tison, Yves Roos	Monotone AC-Tree Automata.	LPAR	2005	DBLP DOI BibTeX RDF	equational tree automata, complexity, decidability, closure properties
9	Brian C. Dean, Michel X. Goemans, Jan Vondrák	Adaptivity and approximation for stochastic packing problems.	SODA	2005	DBLP BibTeX RDF
9	Herman J. ter Horst	Combining RDF and Part of OWL with Rules: Semantics, Decidability, Complexity.	ISWC	2005	DBLP DOI BibTeX RDF
9	Reiner Hähnle, Neil V. Murray, Erik Rosenthal	Normal Forms for Knowledge Compilation.	ISMIS	2005	DBLP DOI BibTeX RDF
9	Jirí Srba	Timed-Arc Petri Nets vs. Networks of Timed Automata.	ICATPN	2005	DBLP DOI BibTeX RDF
9	Jinkui Xie, Linpeng Huang	Specification and Verification of Position Based Routing for Mobile Ad Hoc System.	CIT	2005	DBLP DOI BibTeX RDF
9	Stéphane Demri, David Nowak	Reasoning About Transfinite Sequences.	ATVA	2005	DBLP DOI BibTeX RDF
9	Patricia Bouyer, Fabrice Chevalier, Deepak D'Souza	Fault Diagnosis Using Timed Automata.	FoSSaCS	2005	DBLP DOI BibTeX RDF
9	Yves Bontemps, Pierre-Yves Schobbens	The Complexity of Live Sequence Charts.	FoSSaCS	2005	DBLP DOI BibTeX RDF
9	Yanhui Li, Jianjiang Lu, Baowen Xu, Dazhou Kang, Jixiang Jiang	A Fuzzy Extension of Description Logic ALCH.	MICAI	2005	DBLP DOI BibTeX RDF
9	Dazhou Kang, Jianjiang Lu, Baowen Xu, Yanhui Li, Yanxiang He	Two Reasoning Methods for Extended Fuzzy ALCH.	OTM Conferences (2)	2005	DBLP DOI BibTeX RDF
9	Rimma I. Podlovchenko, Dmitry M. Rusakov, Vladimir A. Zakharov	On the Equivalence Problem for Programs with Mode Switching.	CIAA	2005	DBLP DOI BibTeX RDF
9	Markus Lohrey, Sebastian Maneth	Tree Automata and XPath on Compressed Trees.	CIAA	2005	DBLP DOI BibTeX RDF
9	Michael Benedikt, Wenfei Fan, Floris Geerts	XPath satisfiability in the presence of DTDs.	PODS	2005	DBLP DOI BibTeX RDF
9	Jirí Fiala 0001, Daniël Paulusma, Jan Arne Telle	Algorithms for Comparability of Matrices in Partial Orders Imposed by Graph Homomorphisms.	WG	2005	DBLP DOI BibTeX RDF
9	Marcin Dziubinski, Rineke Verbrugge, Barbara Dunin-Keplicz	Complexity of a theory of collective attitudes in teamwork.	IAT	2005	DBLP DOI BibTeX RDF
9	Gregor Gramlich, Georg Schnitger	Minimizing NFA's and Regular Expressions.	STACS	2005	DBLP DOI BibTeX RDF
9	Jie-Hong Roland Jiang	On Some Transformation Invariants Under Retiming and Resynthesis.	TACAS	2005	DBLP DOI BibTeX RDF
9	Jean-François Condotta, Gérard Ligozat, Stavros Tripakis	Ultimately Periodic Qualitative Constraint Networks for Spatial and Temporal Reasoning.	ICTAI	2005	DBLP DOI BibTeX RDF
9	Paul Gastin, Dietrich Kuske	Uniform Satisfiability Problem for Local Temporal Logics over Mazurkiewicz Traces.	CONCUR	2005	DBLP DOI BibTeX RDF
9	Houda Bel Mokadem, Béatrice Bérard, Patricia Bouyer, François Laroussinie	A New Modality for Almost Everywhere Properties in Timed Automata.	CONCUR	2005	DBLP DOI BibTeX RDF
9	Markus Müller-Olm, Oliver Rüthing, Helmut Seidl	Checking Herbrand Equalities and Beyond.	VMCAI	2005	DBLP DOI BibTeX RDF
9	Floris Geerts, Wenfei Fan	Satisfiability of XPath Queries with Sibling Axes.	DBPL	2005	DBLP DOI BibTeX RDF
9	Béatrice Bérard, Franck Cassez, Serge Haddad, Didier Lime, Olivier H. Roux	When Are Timed Automata Weakly Timed Bisimilar to Time Petri Nets?	FSTTCS	2005	DBLP DOI BibTeX RDF	Weak Timed Bisimilarity, Timed Automata, Time Petri Nets
9	Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans	On the Complexity of Succinct Zero-Sum Games.	CCC	2005	DBLP DOI BibTeX RDF
9	Bill Rosgen	On the Hardness of Distinguishing Mixed-State Quantum Computations.	CCC	2005	DBLP DOI BibTeX RDF
9	Kaile Su, Abdul Sattar 0001, Guido Governatori, Qingliang Chen	A computationally grounded logic of knowledge, belief and certainty.	AAMAS	2005	DBLP DOI BibTeX RDF	computationally grounded model, modal logic, interpreted system
9	Jinkui Xie, Linpeng Huang	Formal Description and Complexity Analysis of Routing in Mobile Ad Hoc System.	PDCAT	2005	DBLP DOI BibTeX RDF
9	Miguel A. Gutiérrez-Naranjo, Mario J. Pérez-Jiménez, Francisco José Romero-Campero	A Linear Solution for QSAT with Membrane Creation.	Workshop on Membrane Computing	2005	DBLP DOI BibTeX RDF
9	Guillem Godoy, Robert Nieuwenhuis, Ashish Tiwari 0001	Classes of term rewrite systems with polynomial confluence problems.	ACM Trans. Comput. Log.	2004	DBLP DOI BibTeX RDF	Rewriting, confluence
9	Stéphane Grumbach, Maurizio Rafanelli, Leonardo Tininini	On the equivalence and rewriting of aggregate queries.	Acta Informatica	2004	DBLP DOI BibTeX RDF
9	Parosh Aziz Abdulla, S. Purushothaman Iyer, Aletta Nylén	SAT-Solving the Coverability Problem for Petri Nets.	Formal Methods Syst. Des.	2004	DBLP DOI BibTeX RDF	Petri nets, unfoldings, coverability, infinite state systems, partial-order methods
9	John H. Reif, Zheng Sun	Movement Planning in the Presence of Flows.	Algorithmica	2004	DBLP DOI BibTeX RDF	Optimization, Robotics, Shortest path, Path planning
9	Dietmar Berwanger, Erich Grädel	Fixed-Point Logics and Solitaire Games.	Theory Comput. Syst.	2004	DBLP DOI BibTeX RDF
9	Shin Aida, Marcel Crâsmaru, Kenneth W. Regan, Osamu Watanabe 0001	Games with Uniqueness Properties.	Theory Comput. Syst.	2004	DBLP DOI BibTeX RDF
9	Volker Diekert, Markus Lohrey	Existential and Positive Theories of Equations in Graph Products.	Theory Comput. Syst.	2004	DBLP DOI BibTeX RDF
9	Carlos Areces, Daniel Gorín	Ordered Resolution with Selection for H(@).	LPAR	2004	DBLP DOI BibTeX RDF
9	Lance Fortnow, Rahul Santhanam	Hierarchy Theorems for Probabilistic Polynomial Time.	FOCS	2004	DBLP DOI BibTeX RDF
9	Markus Lohrey	Word Problems on Compressed Words.	ICALP	2004	DBLP DOI BibTeX RDF
9	Elmar Böhler, Christian Glaßer, Bernhard Schwarz, Klaus W. Wagner	Generation Problems.	MFCS	2004	DBLP DOI BibTeX RDF
9	Libor Polák	Minimalizations of NFA Using the Universal Automaton.	CIAA	2004	DBLP DOI BibTeX RDF
9	Eric Allender, Harry Buhrman, Michal Koucký 0001	What Can be Efficiently Reduced to the K-Random Strings?	STACS	2004	DBLP DOI BibTeX RDF
9	Bernhard Schwarz	The Complexity of Satisfiability Problems over Finite Lattices.	STACS	2004	DBLP DOI BibTeX RDF
9	Nikos Mamoulis, Kostas Stergiou 0001	Algorithms for Quantified Constraint Satisfaction Problems.	CP	2004	DBLP DOI BibTeX RDF
9	Volker Diekert, Paul Gastin	Pure Future Local Temporal Logics Are Expressively Complete for Mazurkiewicz Traces.	LATIN	2004	DBLP DOI BibTeX RDF	concurrency, Temporal logics, Mazurkiewicz traces
9	Manuel Bodirsky, Tobias Gärtner, Timo von Oertzen, Jan Schwinghammer	Effciently Computing the Density of Regular Languages.	LATIN	2004	DBLP DOI BibTeX RDF
9	Krishnendu Chatterjee, Pallab Dasgupta, P. P. Chakrabarti 0001	Complexity of Compositional Model Checking of Computation Tree Logic on Simple Structures.	IWDC	2004	DBLP DOI BibTeX RDF
9	John M. Hitchcock	Small Spans in Scaled Dimension.	CCC	2004	DBLP DOI BibTeX RDF
9	Harry Buhrman, Leen Torenvliet	Separating Complexity Classes Using Structural Properties.	CCC	2004	DBLP DOI BibTeX RDF
9	Thomas Brihaye, Véronique Bruyère, Jean-François Raskin	Model-Checking for Weighted Timed Automata.	FORMATS/FTRTFT	2004	DBLP DOI BibTeX RDF
9	Jirí Srba	Strong bisimilarity of simple process algebras: complexity lower bounds.	Acta Informatica	2003	DBLP DOI BibTeX RDF