Search results for "EXPTIME"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
102	Pei-Chi Wu	On exponential-time completeness of the circularity problem for attribute grammars.	ACM Trans. Program. Lang. Syst.	2004	DBLP DOI BibTeX RDF	EXPTIME-complete, circularity problem, Attribute grammars, alternating Turing machines
60	Olivier Serre	Parity Games Played on Transition Graphs of One-Counter Processes.	FoSSaCS	2006	DBLP DOI BibTeX RDF
60	Hubert Comon, Florent Jacquemard	Ground Reducibility is EXPTIME-Complete.	LICS	1997	DBLP DOI BibTeX RDF
53	Toshiyasu Arai, Naohi Eguchi	A new function algebra of EXPTIME functions by safe nested recursion.	ACM Trans. Comput. Log.	2009	DBLP DOI BibTeX RDF	EXPTIME, Implicit computational complexity
48	Naoki Kobayashi 0001, C.-H. Luke Ong	Complexity of Model Checking Recursion Schemes for Fragments of the Modal Mu-Calculus.	ICALP (2)	2009	DBLP DOI BibTeX RDF
48	Laura Bozzelli	Complexity Results on Branching-Time Pushdown Model Checking.	VMCAI	2006	DBLP DOI BibTeX RDF
48	Nikola Benes, Jan Kretínský, Kim Guldstrand Larsen, Jirí Srba	Checking Thorough Refinement on Modal Transition Systems Is EXPTIME-Complete.	ICTAC	2009	DBLP DOI BibTeX RDF
48	Rajeev Goré, Linh Anh Nguyen	EXPTIME Tableaux with Global Caching for Description Logics with Transitive Roles, Inverse Roles and Role Hierarchies.	TABLEAUX	2007	DBLP DOI BibTeX RDF
41	Rodney G. Downey, André Nies	Undecidability Results for Low Complexity Degree Structures.	CCC	1997	DBLP DOI BibTeX RDF	undecidability results, low complexity degree structures, EXPTIME degrees, polynomial time Turing, many-one reducibility, coding method, ideal lattices, hyper-polynomial time classes, Boolean algebra, Boolean algebras
36	Alessandro Bianco, Fabio Mogavero, Aniello Murano	Graded Computation Tree Logic.	LICS	2009	DBLP DOI BibTeX RDF
36	Balder ten Cate, Carsten Lutz	The complexity of query containment in expressive fragments of XPath 2.0.	PODS	2007	DBLP DOI BibTeX RDF	XML, complexity, satisfiability, XPath, containment
36	Piero A. Bonatti, Carsten Lutz, Aniello Murano, Moshe Y. Vardi	The Complexity of Enriched µ-Calculi.	ICALP (2)	2006	DBLP DOI BibTeX RDF
36	Ulrike Sattler, Moshe Y. Vardi	The Hybrid µ-Calculus.	IJCAR	2001	DBLP DOI BibTeX RDF
36	Salvatore Caporaso, Michele Zito 0001	On a Relation Between Uniform Coding and Problems of the Form DTIMEF(F) =? DSPACEF(F).	Acta Informatica	1998	DBLP DOI BibTeX RDF
36	Serge Abiteboul, Moshe Y. Vardi, Victor Vianu	Fixpoint logics, relational machines, and computational complexity.	J. ACM	1997	DBLP DOI BibTeX RDF	fixpoint logic, relational complexity, computational complexity, complexity classes
36	Linh Anh Nguyen, Andrzej Szalas	ExpTime Tableaux for Checking Satisfiability of a Knowledge Base in the Description Logic ALC\mathcal{ALC}.	ICCCI	2009	DBLP DOI BibTeX RDF
36	Corina Cîrstea, Clemens Kupke, Dirk Pattinson	EXPTIME Tableaux for the Coalgebraic µ-Calculus.	CSL	2009	DBLP DOI BibTeX RDF
29	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
24	Balder ten Cate, Carsten Lutz	The complexity of query containment in expressive fragments of XPath 2.0.	J. ACM	2009	DBLP DOI BibTeX RDF	XML, complexity, satisfiability, XPath, containment
24	Nathalie Bertrand 0001, Blaise Genest, Hugo Gimbert	Qualitative Determinacy and Decidability of Stochastic Games with Signals.	LICS	2009	DBLP DOI BibTeX RDF
24	Naoki Kobayashi 0001	Types and Recursion Schemes for Higher-Order Program Verification.	APLAS	2009	DBLP DOI BibTeX RDF
24	Diego Figueira	Satisfiability of downward XPath with data equality tests.	PODS	2009	DBLP DOI BibTeX RDF	bip automaton, data-tree, infinite alphabet, unranked unordered tree, xpath, xml, data values
24	Stijn Heymans, Davy Van Nieuwenborgh, Dirk Vermeir	Open answer set programming with guarded programs.	ACM Trans. Comput. Log.	2008	DBLP DOI BibTeX RDF	fixed-point logic, open domains, Answer set programming
24	Tomás Brázdil, Vojtech Forejt, Jan Kretínský, Antonín Kucera 0001	The Satisfiability Problem for Probabilistic CTL.	LICS	2008	DBLP DOI BibTeX RDF	temporal logics, Markov chains
24	Andrzej S. Murawski	Reachability Games and Game Semantics: Comparing Nondeterministic Programs.	LICS	2008	DBLP DOI BibTeX RDF	Idealized Algol, pushdown graphs, reachability games, nondeterminism, game semantics
24	Matthew Hague, Andrzej S. Murawski, C.-H. Luke Ong, Olivier Serre	Collapsible Pushdown Automata and Recursion Schemes.	LICS	2008	DBLP DOI BibTeX RDF	Higher-order pushdown automata, game semantics, higher-order recursion schemes
24	Tomás Brázdil, Vojtech Forejt, Antonín Kucera 0001	Controller Synthesis and Verification for Markov Decision Processes with Qualitative Branching Time Objectives.	ICALP (2)	2008	DBLP DOI BibTeX RDF
24	Taolue Chen, Jian Lu 0001	Towards the Complexity of Controls for Timed Automata with a Small Number of Clocks.	FSKD (5)	2008	DBLP DOI BibTeX RDF
24	Pietro Abate, Rajeev Goré, Florian Widmann	One-Pass Tableaux for Computation Tree Logic.	LPAR	2007	DBLP DOI BibTeX RDF
24	Salvatore La Torre, Gennaro Parlato	On the Complexity of LtlModel-Checking of Recursive State Machines.	ICALP	2007	DBLP DOI BibTeX RDF
24	Alessandro Ferrante, Aniello Murano	Enriched µ-Calculi Module Checking.	FoSSaCS	2007	DBLP DOI BibTeX RDF
24	Alessandro Artale, Diego Calvanese, Roman Kontchakov, Vladislav Ryzhikov, Michael Zakharyaschev	Reasoning over Extended ER Models.	ER	2007	DBLP DOI BibTeX RDF
24	Dario Carotenuto, Aniello Murano, Adriano Peron	2-Visibly Pushdown Automata.	Developments in Language Theory	2007	DBLP DOI BibTeX RDF
24	Marcin Jurdzinski, François Laroussinie, Jeremy Sproston	Model Checking Probabilistic Timed Automata with One or Two Clocks.	TACAS	2007	DBLP DOI BibTeX RDF
24	Laura Bozzelli	Alternating Automata and a Temporal Fixpoint Calculus for Visibly Pushdown Languages.	CONCUR	2007	DBLP DOI BibTeX RDF
24	Phokion G. Kolaitis, Jonathan Panttaja, Wang Chiew Tan	The complexity of data exchange.	PODS	2006	DBLP DOI BibTeX RDF	database dependencies, complexity, data exchange, schema mappings, heterogenous databases, undecidability, data translation
24	Ken Kaneiwa, Ken Satoh	Consistency Checking Algorithms for Restricted UML Class Diagrams.	FoIKS	2006	DBLP DOI BibTeX RDF
24	Wiebe van der Hoek, Alessio Lomuscio, Michael J. Wooldridge	On the complexity of practical ATL model checking.	AAMAS	2006	DBLP DOI BibTeX RDF	verification, complexity, cooperation, logic
24	Bernd Finkbeiner, Sven Schewe	Semi-automatic Distributed Synthesis.	ATVA	2005	DBLP DOI BibTeX RDF
24	Andrzej S. Murawski, Igor Walukiewicz	Third-Order Idealized Algol with Iteration Is Decidable.	FoSSaCS	2005	DBLP DOI BibTeX RDF
24	Tomás Brázdil, Antonín Kucera 0001, Oldrich Strazovský	On the Decidability of Temporal Properties of Probabilistic Pushdown Automata.	STACS	2005	DBLP DOI BibTeX RDF
24	Kousha Etessami, Mihalis Yannakakis	Algorithmic Verification of Recursive Probabilistic State Machines.	TACAS	2005	DBLP DOI BibTeX RDF
24	Jean-Michel Couvreur, Nasser Saheb, Grégoire Sutre	An Optimal Automata Approach to LTL Model Checking of Probabilistic Systems.	LPAR	2003	DBLP DOI BibTeX RDF
24	Jan Johannsen, Martin Lange	CTL+ Is Complete for Double Exponential Time.	ICALP	2003	DBLP DOI BibTeX RDF
24	Jan Hladik	Implementation and Optimisation of a Tableau Algorithm for the Guarded Fragment.	TABLEAUX	2002	DBLP DOI BibTeX RDF
24	Antonín Kucera 0001	On Simulation-Checking with Sequential Systems.	ASIAN	2000	DBLP DOI BibTeX RDF
24	Georg Gottlob, Christos H. Papadimitriou	On the Complexity of Single-Rule Datalog Queries.	LPAR	1999	DBLP DOI BibTeX RDF
24	Orna Kupferman, Moshe Y. Vardi	Robust Satisfaction.	CONCUR	1999	DBLP DOI BibTeX RDF
24	Harald Ganzinger, Florent Jacquemard, Margus Veanes	Rigid Reachability.	ASIAN	1998	DBLP DOI BibTeX RDF
24	Anthony J. Bonner	Hypothetical Datalog: Complexity and Expressiblity.	ICDT	1988	DBLP DOI BibTeX RDF
24	Uwe Schöning	Lower Bounds by Recursion Theoretic Arguments (Extended Abstract).	ICALP	1986	DBLP DOI BibTeX RDF
24	Stefan Göller, Pawel Parys	Weak Bisimulation Finiteness of Pushdown Systems With Deterministic ε-Transitions Is 2-EXPTIME-Complete.	SODA	2023	DBLP DOI BibTeX RDF
24	Robin Hirsch, Brett McLean	EXPTIME-hardness of higher-dimensional Minkowski spacetime.	CoRR	2022	DBLP DOI BibTeX RDF
24	Robin Hirsch, Brett McLean	EXPTIME-hardness of higher-dimensional Minkowski spacetime.	AiML	2022	DBLP BibTeX RDF
24	Bartosz Bednarczyk	Statistical EL is ExpTime-complete.	Inf. Process. Lett.	2021	DBLP DOI BibTeX RDF
24	Fumitaka Ito, Masahiko Naito, Naoyuki Katabami, Tatsuie Tsukiji	EXPTIME Hardness of an n by n Custodian Capture Game.	Algorithms	2021	DBLP DOI BibTeX RDF
24	Shohei Mishiba, Yasuhiko Takenaga	QUIXO is EXPTIME-complete.	Inf. Process. Lett.	2020	DBLP DOI BibTeX RDF
24	Mnacho Echenim, Radu Iosif, Nicolas Peltier	Entailment Checking in Separation Logic with Inductive Definitions is 2-EXPTIME hard.	CoRR	2020	DBLP BibTeX RDF
24	Nadia Labai, Magdalena Ortiz 0001, Mantas Simkus	An ExpTime Upper Bound for ALC with Integers (Extended Version).	CoRR	2020	DBLP BibTeX RDF
24	Linh Anh Nguyen	ExpTime Tableaux with Global Caching for Hybrid PDL.	J. Autom. Reason.	2020	DBLP DOI BibTeX RDF
24	Mnacho Echenim, Radu Iosif, Nicolas Peltier	Entailment Checking in Separation Logic with Inductive Definitions is 2-EXPTIME hard.	LPAR	2020	DBLP DOI BibTeX RDF
24	Nadia Labai, Magdalena Ortiz 0001, Mantas Simkus	An ExpTime Upper Bound for ALC with Integers.	KR	2020	DBLP DOI BibTeX RDF
24	Bartosz Bednarczyk	Statistical EL is ExpTime-complete.	CoRR	2019	DBLP BibTeX RDF
24	Corto Mascle, Mahsa Shirmohammadi, Patrick Totzke	Controlling a Random Population is EXPTIME-hard.	CoRR	2019	DBLP BibTeX RDF
24	Agathoklis Kritsimallis, Ioannis Refanidis	ExpTime Tableaux for Type PDL.	CoRR	2019	DBLP BibTeX RDF
24	Artur Niewiadomski 0001, Piotr Switalski, Teofil Sidoruk, Wojciech Penczek	SMT-Solvers in Action: Encoding and Solving Selected Problems in NP and EXPTIME.	Sci. Ann. Comput. Sci.	2018	DBLP BibTeX RDF
24	Linh Anh Nguyen	ExpTime Tableaux with Global Caching for Hybrid PDL.	CoRR	2017	DBLP BibTeX RDF
24	Linh Anh Nguyen	ExpTime Tableaux with Global Caching for Graded Propositional Dynamic Logic.	Fundam. Informaticae	2016	DBLP DOI BibTeX RDF
24	Sylvain Schmitz	Implicational Relevance Logic is 2-EXPTIME-Complete.	J. Symb. Log.	2016	DBLP DOI BibTeX RDF
24		Finite LTL Synthesis is EXPTIME-complete.	CoRR	2016	DBLP BibTeX RDF
24	Carles Creus, Adrià Gascón, Guillem Godoy, Lander Ramos	The HOM Problem is EXPTIME-Complete.	SIAM J. Comput.	2016	DBLP DOI BibTeX RDF
24	Chaodong He, Mingzhang Huang	Branching Bisimilarity on Normed BPA Is EXPTIME-complete.	CoRR	2015	DBLP BibTeX RDF
24	William B. Kinnersley	Cops and Robbers is EXPTIME-complete.	J. Comb. Theory, Ser. B	2015	DBLP DOI BibTeX RDF
24	Chaodong He, Mingzhang Huang	Branching Bisimilarity on Normed BPA Is EXPTIME-Complete.	LICS	2015	DBLP DOI BibTeX RDF
24	Linh Anh Nguyen	ExpTime Tableaux with Global Caching for Graded Propositional Dynamic Logic.	CS&P	2015	DBLP BibTeX RDF
24	Linh Anh Nguyen, Joanna Golinska-Pilarek	An ExpTime Tableau Method for Dealing with Nominals and Qualified Number Restrictions in Deciding the Description Logic SHOQ.	Fundam. Informaticae	2014	DBLP DOI BibTeX RDF
24	Jian Huang 0010, Xinye Zhao, Jianxing Gong	Optimised ExpTime Tableaux for S H I N over Finite Residuated Lattices.	J. Appl. Math.	2014	DBLP DOI BibTeX RDF
24	Linh Anh Nguyen	ExpTime tableaux with global state caching for the description logic SHIO.	Neurocomputing	2014	DBLP DOI BibTeX RDF
24	Sylvain Schmitz	Implicational Relevance Logic is 2-EXPTIME-Complete.	CoRR	2014	DBLP BibTeX RDF
24	Linh Anh Nguyen, Joanna Golinska-Pilarek	ExpTime Tableaux with Global Caching for the Description Logic SHOQ.	CoRR	2014	DBLP BibTeX RDF
24	Walid Belkhir, Yannick Chevalier, Michaël Rusinowitch	An EXPTIME Algorithm for Data-Aware Service Simulation Using Parametrized Automata.	ICSOC Workshops	2014	DBLP DOI BibTeX RDF
24	John Christopher McCabe-Dansted, Mark Reynolds 0001	Fairness with EXPTIME Bundled CTL Tableau.	TIME	2014	DBLP DOI BibTeX RDF
24	Sylvain Schmitz	Implicational Relevance Logic is 2-ExpTime-Complete.	RTA-TLCA	2014	DBLP DOI BibTeX RDF
24	Stefan Kiefer	BPA bisimilarity is EXPTIME-hard.	Inf. Process. Lett.	2013	DBLP DOI BibTeX RDF
24	David Van Horn, Harry G. Mairson	Deciding $k$CFA is complete for EXPTIME.	CoRR	2013	DBLP BibTeX RDF
24	William B. Kinnersley	Cops and Robbers is EXPTIME-complete.	CoRR	2013	DBLP BibTeX RDF
24	Rajeev Goré, Linh Anh Nguyen	ExpTime Tableaux for ALC Using Sound Global Caching.	J. Autom. Reason.	2013	DBLP DOI BibTeX RDF
24	Linh Anh Nguyen, Joanna Golinska-Pilarek	An ExpTime Tableau Method for Dealing with Nominals and Quantified Number Restrictions in Deciding the Description Logic SHOQ.	CS&P	2013	DBLP BibTeX RDF
24	Loris Bozzato, Martin Homola, Luciano Serafini	ExpTime Tableaux Algorithm for Contextualized ALC.	CONTEXT	2013	DBLP DOI BibTeX RDF
24	Linh Anh Nguyen	Cut-Free ExpTime Tableaux for Converse-PDL Extended with Regular Inclusion Axioms.	KES-AMSTA	2013	DBLP DOI BibTeX RDF
24	Roman Kontchakov, Vladislav Ryzhikov, Michael Zakharyaschev	Conjunctive Query Inseparability in OWL 2 QL is ExpTime-hard.	Description Logics	2013	DBLP BibTeX RDF
24	Petr Jancar	Bisimilarity on Basic Process Algebra is in 2-ExpTime (an explicit proof)	Log. Methods Comput. Sci.	2012	DBLP DOI BibTeX RDF
24	Stefan Kiefer	BPA Bisimilarity is EXPTIME-hard	CoRR	2012	DBLP BibTeX RDF
24	Linh Anh Nguyen	ExpTime Tableaux for the Description Logic SHIQ Based on Global State Caching and Integer Linear Feasibility Checking	CoRR	2012	DBLP BibTeX RDF
24	Nikola Benes, Jan Kretínský, Kim G. Larsen, Jirí Srba	EXPTIME-completeness of thorough refinement on modal transition systems.	Inf. Comput.	2012	DBLP DOI BibTeX RDF
24	Carles Creus, Adrià Gascón, Guillem Godoy, Lander Ramos	The HOM Problem is EXPTIME-Complete.	LICS	2012	DBLP DOI BibTeX RDF
24	Linh Anh Nguyen, Andrzej Szalas	ExpTime Tableau Decision Procedures for Regular Grammar Logics with Converse.	Stud Logica	2011	DBLP DOI BibTeX RDF
24	Corina Cîrstea, Clemens Kupke, Dirk Pattinson	EXPTIME Tableaux for the Coalgebraic mu-Calculus	Log. Methods Comput. Sci.	2011	DBLP DOI BibTeX RDF
24	Linh Anh Nguyen	Cut-Free ExpTime Tableaux for Checking Satisfiability of a Knowledge Base in the Description Logic SHI	CoRR	2011	DBLP BibTeX RDF
24	Linh Anh Nguyen	A Cut-Free ExpTime Tableau Decision Procedure for the Logic Extending Converse-PDL with Regular Inclusion Axioms	CoRR	2011	DBLP BibTeX RDF