Search results for "NEXPTIME"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
62	Witold Charatonik, Leszek Pacholski	Set constraints with projections are in NEXPTIME	FOCS	1994	DBLP DOI BibTeX RDF	negated set constraints, NEXPTIME, program analysis, projections, type inference, decidability, set constraints
62	Carsten Lutz	NEXPTIME-Complete Description Logics with Concrete Domains.	IJCAR	2001	DBLP DOI BibTeX RDF
49	Carsten Lutz	NEXP TIME-complete description logics with concrete domains.	ACM Trans. Comput. Log.	2004	DBLP DOI BibTeX RDF	NExpTime-completeness, concrete domains, domino problem, Computational complexity, description logic, post correspondence problem
49	Olivier Gasquet, Bilal Said	Tableaux with Dynamic Filtration for Layered Modal Logics.	TABLEAUX	2007	DBLP DOI BibTeX RDF	Layered Modal Logic, Dynamic Filtration, Satisfaction problem, Complexity, Tableau
49	Leszek Pacholski, Wieslaw Szwast, Lidia Tendera	Complexity of Two-Variable Logic with Counting.	LICS	1997	DBLP DOI BibTeX RDF
46	Siva Anantharaman, Paliath Narendran, Michaël Rusinowitch	ACID-Unification Is NEXPTIME-Decidable.	MFCS	2003	DBLP DOI BibTeX RDF	E-Unification, Dag automata, Complexity, Tree automata, Set constraints
33	Sibylle B. Fröschle	The Insecurity Problem: Tackling Unbounded Data.	CSF	2007	DBLP DOI BibTeX RDF
30	Thomas Brihaye, Véronique Bruyère, Gaspard Reghem	Quantitative Reachability Stackelberg-Pareto Synthesis is NEXPTIME-Complete.	CoRR	2023	DBLP DOI BibTeX RDF
30	Thomas Brihaye, Véronique Bruyère, Gaspard Reghem	Quantitative Reachability Stackelberg-Pareto Synthesis Is NEXPTIME-Complete.	RP	2023	DBLP DOI BibTeX RDF
30	Nian-Ze Lee, Jie-Hong R. Jiang	Dependency Stochastic Boolean Satisfiability: A Logical Formalism for NEXPTIME Decision Problems with Uncertainty.	AAAI	2021	DBLP DOI BibTeX RDF
30	Nian-Ze Lee, Jie-Hong R. Jiang	Dependency Stochastic Boolean Satisfiability: A Logical Formalism for NEXPTIME Decision Problems with Uncertainty.	CoRR	2019	DBLP BibTeX RDF
30	Christopher H. Broadbent, Arnaud Carayol, Matthew Hague, Olivier Serre	Emptiness of Stack Automata is NEXPTIME-complete: A Correction.	CoRR	2018	DBLP BibTeX RDF
30	Marco Voigt, Christoph Weidenbach	Bernays-Schönfinkel-Ramsey with Simple Bounds is NEXPTIME-complete.	CoRR	2015	DBLP BibTeX RDF
30	Wojciech Czerwinski, Petr Jancar	Branching Bisimilarity of Normed BPA Processes Is in NEXPTIME.	LICS	2015	DBLP DOI BibTeX RDF
30	Wojciech Czerwinski, Petr Jancar	Branching Bisimilarity of Normed BPA Processes is in NEXPTIME.	CoRR	2014	DBLP BibTeX RDF
30	Michal Zawidzki, Renate A. Schmidt, Dmitry Tishkovsky	Satisfiability problem for modal logic with global counting operators coded in binary is NExpTime-complete.	Inf. Process. Lett.	2013	DBLP DOI BibTeX RDF
30	Guillaume Aucher, Bastien Maubert, François Schwarzentruber	Tableau Method and NEXPTIME-Completeness of DEL-Sequents.	M4M/LAMAS	2011	DBLP DOI BibTeX RDF
30	Ross Willard	PP-DEFINABILITY IS CO-NEXPTIME-COMPLETE.	The Constraint Satisfaction Problem: Complexity and Approximability	2009	DBLP BibTeX RDF
30	Ferucio Laurentiu Tiplea, Catalin V. Bîrjoveanu, Constantin Enea, Ioana Boureanu	Secrecy for bounded security protocols with freshness check is NEXPTIME-complete.	J. Comput. Secur.	2008	DBLP DOI BibTeX RDF
30	Anatoly Petrovich Beltiukov	The set of the true regular protothetics formulas with partially ordered quantifiers is NEXPTIME-complete.	Ann. Pure Appl. Log.	2001	DBLP DOI BibTeX RDF
30	Wojciech Plandowski	Satisfiability of Word Equations with Constants is in NEXPTIME.	STOC	1999	DBLP DOI BibTeX RDF
30	Stephan Tobies	A NExpTime-Complete Description Logic Strictly Contained in C2.	CSL	1999	DBLP DOI BibTeX RDF
30	Pawel Mielniczuk, Leszek Pacholski	Tarskian Set Constraints Are in NEXPTIME.	MFCS	1998	DBLP DOI BibTeX RDF
30	Patrick Lincoln, Andre Scedrov	First-Order Linear Logic without Modalities is NEXPTIME-Hard.	Theor. Comput. Sci.	1994	DBLP DOI BibTeX RDF
30	Kjartan Stefánsson	Systems of Set Constraints with Negative Constraints are NEXPTIME-Complete	LICS	1994	DBLP DOI BibTeX RDF
30	Juris Hartmanis, Neil Immerman, Vivian Sewelson	Sparse Sets in NP-P: EXPTIME versus NEXPTIME	Inf. Control.	1985	DBLP DOI BibTeX RDF
30	Juris Hartmanis, Vivian Sewelson, Neil Immerman	Sparse Sets in NP-P: EXPTIME versus NEXPTIME	STOC	1983	DBLP DOI BibTeX RDF
16	Béatrice Bérard, Serge Haddad	Interrupt Timed Automata.	FoSSaCS	2009	DBLP DOI BibTeX RDF	decidability of reachability, timed automata, interruptions, Hybrid automata, multi-task systems
16	Mark Kaminski, Sigurd Schneider, Gert Smolka	Terminating Tableaux for Graded Hybrid Logic with Global Modalities and Role Hierarchies.	TABLEAUX	2009	DBLP DOI BibTeX RDF
16	Davide Bresolin, Angelo Montanari, Pietro Sala, Guido Sciavicco	A Tableau-Based System for Spatial Reasoning about Directional Relations.	TABLEAUX	2009	DBLP DOI BibTeX RDF
16	Siva Anantharaman, Hai Lin 0005, Christopher Lynch, Paliath Narendran, Michaël Rusinowitch	Unification Modulo Homomorphic Encryption.	FroCoS	2009	DBLP DOI BibTeX RDF
16	Helmut Seidl, Kumar Neeraj Verma	Flat and one-variable clauses: Complexity of verifying cryptographic protocols with single blind copying.	ACM Trans. Comput. Log.	2008	DBLP DOI BibTeX RDF	instantiation-based theorem proving, Cryptographic protocols, first-order logic, resolution, Horn clauses
16	Michael Benedikt, Wenfei Fan, Floris Geerts	XPath satisfiability in the presence of DTDs.	J. ACM	2008	DBLP DOI BibTeX RDF	XML, Satisfiability, XPath, Containment, DTDs
16	Birte Glimm, Yevgeny Kazakov	Role Conjunctions in Expressive Description Logics.	LPAR	2008	DBLP DOI BibTeX RDF
16	Roman Kontchakov, Ian Pratt-Hartmann, Frank Wolter, Michael Zakharyaschev	On the Computational Complexity of Spatial Logics with Connectedness Constraints.	LPAR	2008	DBLP DOI BibTeX RDF
16	Andrea Calì, Davide Martinenghi	Conjunctive Query Containment under Access Limitations.	ER	2008	DBLP DOI BibTeX RDF
16	Davide Bresolin, Angelo Montanari, Pietro Sala, Guido Sciavicco	Optimal Tableaux for Right Propositional Neighborhood Logic over Linear Orders.	JELIA	2008	DBLP DOI BibTeX RDF
16	Dietrich Kuske, Markus Lohrey	Hamiltonicity of automatic graphs.	IFIP TCS	2008	DBLP DOI BibTeX RDF
16	Pierre McKenzie, Klaus W. Wagner	The Complexity of Membership Problems for Circuits Over Sets of Natural Numbers.	Comput. Complex.	2007	DBLP DOI BibTeX RDF	Subject classification. 68Q25, 68Q15, 03D15
16	Davide Bresolin, Angelo Montanari, Guido Sciavicco	An Optimal Decision Procedure for Right Propositional Neighborhood Logic.	J. Autom. Reason.	2007	DBLP DOI BibTeX RDF	tableaux-based decision procedures, right propositional neighborhood logic, interval temporal logic
16	Renate A. Schmidt, Dmitry Tishkovsky	Using Tableau to Decide Expressive Description Logics with Role Negation.	ISWC/ASWC	2007	DBLP DOI BibTeX RDF
16	Detlef Kähler, Ralf Küsters, Tomasz Truderung	Infinite State AMC-Model Checking for Cryptographic Protocols.	LICS	2007	DBLP DOI BibTeX RDF
16	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
16	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
16	Davide Bresolin, Angelo Montanari, Pietro Sala	An Optimal Tableau-Based Decision Algorithm for Propositional Neighborhood Logic.	STACS	2007	DBLP DOI BibTeX RDF
16	Antonio Morales Nicolás, Isabel Navarrete, Guido Sciavicco	Using Temporal Logic for Spatial Reasoning: Temporalized Propositional Neighborhood Logic.	EUROCAST	2007	DBLP DOI BibTeX RDF
16	Uwe Bubeck, Hans Kleine Büning	Dependency Quantified Horn Formulas: Models and Complexity.	SAT	2006	DBLP DOI BibTeX RDF
16	Ian Pratt-Hartmann	Complexity of the Two-Variable Fragment with Counting Quantifiers.	J. Log. Lang. Inf.	2005	DBLP DOI BibTeX RDF	Abstract two-variable fragment, counting quantifiers, complexity, logic
16	Haruo Hosoya, Alain Frisch, Giuseppe Castagna	Parametric polymorphism for XML.	POPL	2005	DBLP DOI BibTeX RDF	XML, polymorphism, subtyping, tree automata
16	Michael Benedikt, Wenfei Fan, Floris Geerts	XPath satisfiability in the presence of DTDs.	PODS	2005	DBLP DOI BibTeX RDF
16	Tomasz Truderung	Regular Protocols and Attacks with Regular Knowledge.	CADE	2005	DBLP DOI BibTeX RDF
16	Tomasz Truderung	Selecting Theories and Recursive Protocols.	CONCUR	2005	DBLP DOI BibTeX RDF
16	Emanuel Kieronski	Results on the Guarded Fragment with Equivalence or Transitive Relations.	CSL	2005	DBLP DOI BibTeX RDF
16	Thomas Eiter, Wolfgang Faber 0001, Nicola Leone, Gerald Pfeifer, Axel Polleres	A logic programming approach to knowledge-state planning: Semantics and complexity.	ACM Trans. Comput. Log.	2004	DBLP DOI BibTeX RDF	conformant planning, declarative planning, knowledge-states, secure planning, computational complexity, incomplete information, Answer sets
16	Ian Pratt-Hartmann	Fragments of Language.	J. Log. Lang. Inf.	2004	DBLP DOI BibTeX RDF	decidable fragments, computational complexity, semantics, logic
16	Siva Anantharaman, Paliath Narendran, Michaël Rusinowitch	Unification Modulo ACUI Plus Distributivity Axioms.	J. Autom. Reason.	2004	DBLP DOI BibTeX RDF	equational unification, counter machines, complexity, decidability, rewriting, set constraints, Post correspondence problem
16	Helmut Seidl, Kumar Neeraj Verma	Flat and One-Variable Clauses: Complexity of Verifying Cryptographic Protocols with Single Blind Copying.	LPAR	2004	DBLP DOI BibTeX RDF
16	Stephen D. Travers	The Complexity of Membership Problems for Circuits over Sets of Integers.	MFCS	2004	DBLP DOI BibTeX RDF
16	Ian Pratt-Hartmann	Temporal Prepositions and Their Logic.	TIME	2004	DBLP DOI BibTeX RDF
16	Siva Anantharaman, Paliath Narendran, Michaël Rusinowitch	Unification Modulo ACU I Plus Homomorphisms/Distributivity.	CADE	2003	DBLP DOI BibTeX RDF	E-Unification, Rewrite reachability, Minskymachine, Complexity, Set constraints, Post correspondence problem
16	Pierre McKenzie, Klaus W. Wagner	The Complexity of Membership Problems for Circuits over Sets of Natural Numbers.	STACS	2003	DBLP DOI BibTeX RDF
16	Emanuel Kieronski	EXPSPACE-Complete Variant of Guarded Fragment with Transitivity.	STACS	2002	DBLP DOI BibTeX RDF
16	Witold Charatonik, Jean-Marc Talbot	Atomic Set Constraints with Projection.	RTA	2002	DBLP DOI BibTeX RDF
16	Jean Goubault-Larrecq	Higher-Order Positive Set Constraints.	CSL	2002	DBLP DOI BibTeX RDF
16	Christopher Lynch, Barbara Morawska 0001	Complexity of Linear Standard Theories.	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	Wojciech Plandowski	Satisfiability of Word Equations with Constants is in PSPACE.	FOCS	1999	DBLP DOI BibTeX RDF	word equations
16	Martin Müller 0001, Joachim Niehren, Andreas Podelski	Inclusion Constraints over Non-empty Sets of Trees.	TAPSOFT	1997	DBLP DOI BibTeX RDF
16	Giuseppe De Giacomo, Fabio Massacci	Tableaux and Algorithms for Propositional Dynamic Logic with Converse.	CADE	1996	DBLP DOI BibTeX RDF
16	Surajit Chaudhuri, Moshe Y. Vardi	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs.	PODS	1994	DBLP DOI BibTeX RDF	Datalog
16	Gerhard Buntrock, Krzysztof Lorys	The Variable Membership Problem: Succinctness Versus Complexity.	STACS	1994	DBLP DOI BibTeX RDF
16	Jerzy Tiuryn, Mitchell Wand	Type Reconstruction with Recursive Types and Atomic Subtyping.	TAPSOFT	1993	DBLP DOI BibTeX RDF
16	Deborah Joseph, Meera Sitharam	Kolmogorov Complexity, Restrited Nondeterminism and Generalized Spectra.	STACS	1990	DBLP DOI BibTeX RDF