Search results for "EXPTIME-complete"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
119	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
69	Hubert Comon, Florent Jacquemard	Ground Reducibility is EXPTIME-Complete.	LICS	1997	DBLP DOI BibTeX RDF
64	Olivier Serre	Parity Games Played on Transition Graphs of One-Counter Processes.	FoSSaCS	2006	DBLP DOI BibTeX RDF
57	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
57	Laura Bozzelli	Complexity Results on Branching-Time Pushdown Model Checking.	VMCAI	2006	DBLP DOI BibTeX RDF
42	Piero A. Bonatti, Carsten Lutz, Aniello Murano, Moshe Y. Vardi	The Complexity of Enriched µ-Calculi.	ICALP (2)	2006	DBLP DOI BibTeX RDF
40	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
38	Alessandro Bianco, Fabio Mogavero, Aniello Murano	Graded Computation Tree Logic.	LICS	2009	DBLP DOI BibTeX RDF
38	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
35	Salvatore La Torre, Gennaro Parlato	On the Complexity of LtlModel-Checking of Recursive State Machines.	ICALP	2007	DBLP DOI BibTeX RDF
32	Marcin Jurdzinski, François Laroussinie, Jeremy Sproston	Model Checking Probabilistic Timed Automata with One or Two Clocks.	TACAS	2007	DBLP DOI BibTeX RDF
32	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
32	Uwe Schöning	Lower Bounds by Recursion Theoretic Arguments (Extended Abstract).	ICALP	1986	DBLP DOI BibTeX RDF
31	Stefan Göller, Pawel Parys	Weak Bisimulation Finiteness of Pushdown Systems With Deterministic ε-Transitions Is 2-EXPTIME-Complete.	SODA	2023	DBLP DOI BibTeX RDF
31	Bartosz Bednarczyk	Statistical EL is ExpTime-complete.	Inf. Process. Lett.	2021	DBLP DOI BibTeX RDF
31	Shohei Mishiba, Yasuhiko Takenaga	QUIXO is EXPTIME-complete.	Inf. Process. Lett.	2020	DBLP DOI BibTeX RDF
31	Bartosz Bednarczyk	Statistical EL is ExpTime-complete.	CoRR	2019	DBLP BibTeX RDF
31	Sylvain Schmitz	Implicational Relevance Logic is 2-EXPTIME-Complete.	J. Symb. Log.	2016	DBLP DOI BibTeX RDF
31		Finite LTL Synthesis is EXPTIME-complete.	CoRR	2016	DBLP BibTeX RDF
31	Carles Creus, Adrià Gascón, Guillem Godoy, Lander Ramos	The HOM Problem is EXPTIME-Complete.	SIAM J. Comput.	2016	DBLP DOI BibTeX RDF
31	Chaodong He, Mingzhang Huang	Branching Bisimilarity on Normed BPA Is EXPTIME-complete.	CoRR	2015	DBLP BibTeX RDF
31	William B. Kinnersley	Cops and Robbers is EXPTIME-complete.	J. Comb. Theory, Ser. B	2015	DBLP DOI BibTeX RDF
31	Chaodong He, Mingzhang Huang	Branching Bisimilarity on Normed BPA Is EXPTIME-Complete.	LICS	2015	DBLP DOI BibTeX RDF
31	Sylvain Schmitz	Implicational Relevance Logic is 2-EXPTIME-Complete.	CoRR	2014	DBLP BibTeX RDF
31	Sylvain Schmitz	Implicational Relevance Logic is 2-ExpTime-Complete.	RTA-TLCA	2014	DBLP DOI BibTeX RDF
31	William B. Kinnersley	Cops and Robbers is EXPTIME-complete.	CoRR	2013	DBLP BibTeX RDF
31	Carles Creus, Adrià Gascón, Guillem Godoy, Lander Ramos	The HOM Problem is EXPTIME-Complete.	LICS	2012	DBLP DOI BibTeX RDF
31	Omer Giménez, Guillem Godoy, Sebastian Maneth	Deciding Regularity of the Set of Instances of a Set of Terms with Regular Constraints is EXPTIME-Complete.	SIAM J. Comput.	2011	DBLP DOI BibTeX RDF
31	Alexander Hertel, Alasdair Urquhart	Comments on ECCC Report TR06-133: The Resolution Width Problem is EXPTIME-Complete.	Electron. Colloquium Comput. Complex.	2009	DBLP BibTeX RDF
31	Omer Giménez, Guillem Godoy, Sebastian Maneth	Deciding Regularity of the Set of Instances of a Set of Terms with Regular Constraints is EXPTIME-Complete	CoRR	2009	DBLP BibTeX RDF
31	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
31	Dragan Masulovic	Genclo and Termequiv are EXPTIME-Complete.	Int. J. Algebra Comput.	2008	DBLP DOI BibTeX RDF
31	Adam Antonik, Michael Huth 0001, Kim Guldstrand Larsen, Ulrik Nyman, Andrzej Wasowski	EXPTIME-complete Decision Problems for Modal and Mixed Specifications.	EXPRESS	2008	DBLP DOI BibTeX RDF
31	Marcin Kozik	A finite set of functions with an EXPTIME-complete composition problem.	Theor. Comput. Sci.	2008	DBLP DOI BibTeX RDF
31	Stéphane Demri, Ewa Orlowska	Relative Nondeterministic Information Logic is EXPTIME-complete.	Fundam. Informaticae	2007	DBLP BibTeX RDF
31	Mikhail N. Rybakov	Complexity of finite-variable fragments M of EXPTIME-complete logics.	J. Appl. Non Class. Logics	2007	DBLP DOI BibTeX RDF
31	Alexander Hertel, Alasdair Urquhart	The Resolution Width Problem is EXPTIME-Complete.	Electron. Colloquium Comput. Complex.	2006	DBLP BibTeX RDF
31	Dirk Walther 0002, Carsten Lutz, Frank Wolter, Michael J. Wooldridge	ATL Satisfiability is Indeed EXPTIME-complete.	J. Log. Comput.	2006	DBLP DOI BibTeX RDF
31	Takayuki Yato, Takahiro Seta, Tsuyoshi Ito	Finding Yozume of Generalized Tsume-Shogi is Exptime-Complete.	IEICE Trans. Fundam. Electron. Commun. Comput. Sci.	2005	DBLP DOI BibTeX RDF
31	Hubert Comon, Florent Jacquemard	Ground reducibility is EXPTIME-complete.	Inf. Comput.	2003	DBLP DOI BibTeX RDF
31	J. M. Robson	N by N Checkers is Exptime Complete.	SIAM J. Comput.	1984	DBLP DOI BibTeX RDF
30	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
30	Laura Bozzelli	Alternating Automata and a Temporal Fixpoint Calculus for Visibly Pushdown Languages.	CONCUR	2007	DBLP DOI BibTeX RDF
30	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
30	Bernd Finkbeiner, Sven Schewe	Semi-automatic Distributed Synthesis.	ATVA	2005	DBLP DOI BibTeX RDF
30	Georg Gottlob, Christos H. Papadimitriou	On the Complexity of Single-Rule Datalog Queries.	LPAR	1999	DBLP DOI BibTeX RDF
30	Orna Kupferman, Moshe Y. Vardi	Robust Satisfaction.	CONCUR	1999	DBLP DOI BibTeX RDF
28	Naoki Kobayashi 0001	Types and Recursion Schemes for Higher-Order Program Verification.	APLAS	2009	DBLP DOI BibTeX RDF
28	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
28	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
28	Pietro Abate, Rajeev Goré, Florian Widmann	One-Pass Tableaux for Computation Tree Logic.	LPAR	2007	DBLP DOI BibTeX RDF
28	Alessandro Artale, Diego Calvanese, Roman Kontchakov, Vladislav Ryzhikov, Michael Zakharyaschev	Reasoning over Extended ER Models.	ER	2007	DBLP DOI BibTeX RDF
28	Jan Hladik	Implementation and Optimisation of a Tableau Algorithm for the Guarded Fragment.	TABLEAUX	2002	DBLP DOI BibTeX RDF
28	Antonín Kucera 0001	On Simulation-Checking with Sequential Systems.	ASIAN	2000	DBLP DOI BibTeX RDF
28	Harald Ganzinger, Florent Jacquemard, Margus Veanes	Rigid Reachability.	ASIAN	1998	DBLP DOI BibTeX RDF
26	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
26	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
26	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
26	Alessandro Ferrante, Aniello Murano	Enriched µ-Calculi Module Checking.	FoSSaCS	2007	DBLP DOI BibTeX RDF
26	Dario Carotenuto, Aniello Murano, Adriano Peron	2-Visibly Pushdown Automata.	Developments in Language Theory	2007	DBLP DOI BibTeX RDF
26	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
26	Kousha Etessami, Mihalis Yannakakis	Algorithmic Verification of Recursive Probabilistic State Machines.	TACAS	2005	DBLP DOI BibTeX RDF
23	Harry G. Mairson, Kazushige Terui	On the Computational Complexity of Cut-Elimination in Linear Logic.	ICTCS	2003	DBLP DOI BibTeX RDF
20	Volker Weber	On the Complexity of Branching-Time Logics.	CSL	2009	DBLP DOI BibTeX RDF	complexity of satisfiability, pebble automata, alternating tree automata, forgettable past, CTL, branching-time logic
20	Sven Schewe, Bernd Finkbeiner	Synthesis of Asynchronous Systems.	LOPSTR	2006	DBLP DOI BibTeX RDF
20	Rajeev Alur, Salvatore La Torre	Deterministic generators and games for Ltl fragments.	ACM Trans. Comput. Log.	2004	DBLP DOI BibTeX RDF	Games, Temporal Logic, Automata
18	Patrice Godefroid, Nir Piterman	LTL Generalized Model Checking Revisited.	VMCAI	2009	DBLP DOI BibTeX RDF
18	Birte Glimm, Yevgeny Kazakov	Role Conjunctions in Expressive Description Logics.	LPAR	2008	DBLP DOI BibTeX RDF
18	Rajeev Alur, Marcelo Arenas, Pablo Barceló, Kousha Etessami, Neil Immerman, Leonid Libkin	First-Order and Temporal Logics for Nested Words.	LICS	2007	DBLP DOI BibTeX RDF
18	Jirí Srba	Visibly Pushdown Automata: From Language Equivalence to Simulation and Bisimulation.	CSL	2006	DBLP DOI BibTeX RDF
18	Marcin Dziubinski, Rineke Verbrugge, Barbara Dunin-Keplicz	Complexity of a theory of collective attitudes in teamwork.	IAT	2005	DBLP DOI BibTeX RDF
18	Ian Pratt-Hartmann	Fragments of Language.	J. Log. Lang. Inf.	2004	DBLP DOI BibTeX RDF	decidable fragments, computational complexity, semantics, logic
18	Anatoli Degtyarev, Yuri Gurevich, Paliath Narendran, Margus Veanes, Andrei Voronkov	The Decidability of Simultaneous Rigid E-Unification with One Variable.	RTA	1998	DBLP DOI BibTeX RDF
16	Florent Jacquemard, Michaël Rusinowitch	Rewrite-based verification of XML updates.	PPDP	2010	DBLP DOI BibTeX RDF	hedge automata, static typechecking, xml access control policies, xml updates, term rewriting
16	Lijun Wu, Jinshu Su, Xiangyu Luo, Zhihua Yang, Qingliang Chen	A Concurrent Dynamic Logic of Knowledge, Belief and Certainty for Multi-agent Systems.	Canadian AI	2009	DBLP DOI BibTeX RDF
16	Marcelo Arenas, Pablo Barceló, Juan L. Reutter	Query languages for data exchange: beyond unions of conjunctive queries.	ICDT	2009	DBLP DOI BibTeX RDF
16	Marcin Jurdzinski, Marta Z. Kwiatkowska, Gethin Norman, Ashutosh Trivedi 0001	Concavely-Priced Probabilistic Timed Automata.	CONCUR	2009	DBLP DOI BibTeX RDF
16	Balder ten Cate, Luc Segoufin	XPath, transitive closure logic, and nested tree walking automata.	PODS	2008	DBLP DOI BibTeX RDF	tree walking automata, xpath, xml, transitive closure
16	Carsten Lutz	The Complexity of Conjunctive Query Answering in Expressive Description Logics.	IJCAR	2008	DBLP DOI BibTeX RDF
16	Dirk Walther 0002, Wiebe van der Hoek, Michael J. Wooldridge	Alternating-time temporal logic with explicit strategies.	TARK	2007	DBLP DOI BibTeX RDF
16	Rajeev Alur, Pavol Cerný, Swarat Chaudhuri	Model Checking on Trees with Path Equivalences.	TACAS	2007	DBLP DOI BibTeX RDF
16	Philipp Rohde	On the µ-Calculus Augmented with Sabotage.	FoSSaCS	2006	DBLP DOI BibTeX RDF
16	Rajeev Alur, Salvatore La Torre, P. Madhusudan	Modular Strategies for Infinite Games on Recursive Graphs.	CAV	2003	DBLP DOI BibTeX RDF
16	Rajeev Alur, Salvatore La Torre, P. Madhusudan	Modular Strategies for Recursive Game Graphs.	TACAS	2003	DBLP DOI BibTeX RDF
16	Maria Sorea	A Decidable Fixpoint Logic for Time-Outs.	CONCUR	2002	DBLP DOI BibTeX RDF
16	Franz Baader, Ralf Küsters	Unification in a Description Logic with Transitive Closure of Roles.	LPAR	2001	DBLP DOI BibTeX RDF
16	Carsten Lutz, Ulrike Sattler, Frank Wolter	Modal Logic and the Two-Variable Fragment.	CSL	2001	DBLP DOI BibTeX RDF
16	Igor Walukiewicz	Model Checking CTL Properties of Pushdown Systems.	FSTTCS	2000	DBLP DOI BibTeX RDF
16	Erich Grädel, Igor Walukiewicz	Guarded Fixed Point Logic.	LICS	1999	DBLP DOI BibTeX RDF
16	Véronique Cortier, Harald Ganzinger, Florent Jacquemard, Margus Veanes	Decidable Fragments of Simultaneous Rigid Reachability.	ICALP	1999	DBLP DOI BibTeX RDF
14	Matthew Might, Yannis Smaragdakis, David Van Horn	Resolving and exploiting the k-CFA paradox: illuminating functional vs. object-oriented program analysis.	PLDI	2010	DBLP DOI BibTeX RDF	k-cfa, m-cfa, object-oriented, static analysis, functional, pointer analysis, control-flow analysis
14	Alessandro Ferrante, Margherita Napoli, Mimmo Parente	Graded-CTL: Satisfiability and Symbolic Model Checking.	ICFEM	2009	DBLP DOI BibTeX RDF
14	Naoki Kobayashi 0001, C.-H. Luke Ong	A Type System Equivalent to the Modal Mu-Calculus Model Checking of Higher-Order Recursion Schemes.	LICS	2009	DBLP DOI BibTeX RDF
14	Artur Jez, Alexander Okhotin	One-Nonterminal Conjunctive Grammars over a Unary Alphabet.	CSR	2009	DBLP DOI BibTeX RDF
14	Phiniki Stouppa, Thomas Studer	Data Privacy for Knowledge Bases.	LFCS	2009	DBLP DOI BibTeX RDF
14	Alessandro Ferrante, Margherita Napoli, Mimmo Parente	CTLModel-Checking with Graded Quantifiers.	ATVA	2008	DBLP DOI BibTeX RDF
14	Adila Krisnadhi, Carsten Lutz	Data Complexity in the EL Family of Description Logics.	LPAR	2007	DBLP DOI BibTeX RDF
14	Mantas Simkus, Thomas Eiter	\mathbbFDNC: Decidable Non-monotonic Disjunctive Logic Programs with Function Symbols.	LPAR	2007	DBLP DOI BibTeX RDF
14	Marcin Jurdzinski, Ashutosh Trivedi 0001	Reachability-Time Games on Timed Automata.	ICALP	2007	DBLP DOI BibTeX RDF
14	Carsten Lutz, Frank Wolter	Conservative Extensions in the Lightweight Description Logic EL.	CADE	2007	DBLP DOI BibTeX RDF