Search results for "NP-completeness"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
17	Uffe Engberg, Glynn Winskel	Completeness Results for Linear Logic on Petri Nets.	MFCS	1993	DBLP DOI BibTeX RDF
17	Jennifer Widom, David Gries, Fred B. Schneider	Trace-Based Network Proof Systems: Expressiveness and Completeness.	ACM Trans. Program. Lang. Syst.	1992	DBLP DOI BibTeX RDF	trace logics, temporal logics, safety properties, process networks
17	Juan Carlos González Moreno, Maria Teresa Hortalá-González, Mario Rodríguez-Artalejo	On the Completeness of Narrowing as the Operational Semantics of Functional Logic Programming.	CSL	1992	DBLP DOI BibTeX RDF
17	Andrei Voronkov	On Completeness of Program Synthesis Systems.	CSL	1991	DBLP DOI BibTeX RDF
17	Jan Friso Groote	A New Strategy for Proving omega-Completeness applied to Process Algebra.	CONCUR	1990	DBLP DOI BibTeX RDF
17	Alexandra Poulovassilis, Peter J. H. King	Extending the Functional Data Model to Computational Completeness.	EDBT	1990	DBLP DOI BibTeX RDF
17	Daniel Leivant, Tim Fernando	Meager and replete failures of relative completeness.	J. ACM	1988	DBLP DOI BibTeX RDF
17	Hubert Wagener	On the Emptiness Problem of Tree Automata and Completeness of Modal Logics of Programs.	CSL	1988	DBLP DOI BibTeX RDF
17	Satoru Miyano	The Lexicographically First Maximal Subgraph Problems: P-Completeness and NC Algorithms.	ICALP	1987	DBLP DOI BibTeX RDF
17	Rodney R. Howell, Louis E. Rosier	Completeness Rules for Reachability, Containment, and Equivalence, with Respect to Conflict-Free Vector Replacement Systems.	ICALP	1987	DBLP DOI BibTeX RDF
17	Ernst-Erich Doberkat	Topological Completeness in an Ideal Model for Polymorphic Types.	MFPS	1987	DBLP DOI BibTeX RDF
17	Deepak Kapur, Paliath Narendran	NP-Completeness of the Set Unification and Matching Problems.	CADE	1986	DBLP DOI BibTeX RDF
17	Mario Coppo, Elio Giovannetti	Completeness Results for a Polymorphic Type System.	CAAP	1983	DBLP DOI BibTeX RDF
17	Peter Padawitz	New Results on Completeness and Consistency of Abstract Data Types.	MFCS	1980	DBLP DOI BibTeX RDF
17	Helga Noll	A Note on Resolution: How to Get Rid of Factoring without Loosing Completeness.	CADE	1980	DBLP DOI BibTeX RDF	theorem proving, factoring, first order logic, resolution
17	Rohit Parikh	The Completeness of Propositional Dynamic Logic.	MFCS	1978	DBLP DOI BibTeX RDF
16	Emma Enström, Viggo Kann	Computer lab work on theory.	ITiCSE	2010	DBLP DOI BibTeX RDF	computer lab work, learning theoretical computer science, reductions
16	Liang Zhao 0022, Xiaojian Liu, Zhiming Liu 0001, Zongyan Qiu	Graph transformations for object-oriented refinement.	Formal Aspects Comput.	2009	DBLP DOI BibTeX RDF	Class graph, Structure refinement, Object-orientation, Graph transformation, Normal form, Object graph
16	Clemens Ley, Michael Benedikt	How big must complete XML query languages be?	ICDT	2009	DBLP DOI BibTeX RDF
16	Hirotada Kobayashi	General Properties of Quantum Zero-Knowledge Proofs.	TCC	2008	DBLP DOI BibTeX RDF
16	Ben He, Craig Macdonald, Iadh Ounis	Retrieval sensitivity under training using different measures.	SIGIR	2008	DBLP DOI BibTeX RDF	binary preference, inferred average precision, mean average precision, normalised discounted cumulative gain, relevance judgements, evaluation, training, optimisation
16	Martin Giese	Superposition-based Equality Handling for Analytic Tableaux.	J. Autom. Reason.	2007	DBLP DOI BibTeX RDF	superposition rules, equality handling, analytic tableaux
16	Panagiotis G. Ipeirotis, Eugene Agichtein, Pranay Jain, Luis Gravano	Towards a query optimizer for text-centric tasks.	ACM Trans. Database Syst.	2007	DBLP DOI BibTeX RDF	text database selection, information extraction, distributed information retrieval, Metasearching, focused crawling
16	Azzah Al-Maskari	Beyond classical measures: how to evaluate the effectiveness of interactive information retrieval system?	SIGIR	2007	DBLP DOI BibTeX RDF	IR effectiveness measures, interactive IR evaluation, user satisfaction
16	Rémi Brochenin, Stéphane Demri, Étienne Lozes	Reasoning About Sequences of Memory States.	LFCS	2007	DBLP DOI BibTeX RDF
16	Horacio L. Arló-Costa, Eric Pacuit	First-Order Classical Modal Logic.	Stud Logica	2006	DBLP DOI BibTeX RDF	First-order modal logic, neighborhood semantics, general frames
16	Panagiotis G. Ipeirotis, Eugene Agichtein, Pranay Jain, Luis Gravano	To search or to crawl?: towards a query optimizer for text-centric tasks.	SIGMOD Conference	2006	DBLP DOI BibTeX RDF	information extraction, query optimization, research, metasearching, focused crawling, text databases
16	Maria Luisa Bonet, Jordi Levy, Felip Manyà	A Complete Calculus for Max-SAT.	SAT	2006	DBLP DOI BibTeX RDF
16	Paul Hunter, Anuj Dawar	Complexity Bounds for Regular Games.	MFCS	2005	DBLP DOI BibTeX RDF
16	Horacio L. Arló-Costa, Eric Pacuit	First-order classical modal logic: applications in logics of knowledge and probability.	TARK	2005	DBLP BibTeX RDF
16	Yuval Marom, Ingrid Zukerman	Analysis and Synthesis of Help-Desk Responses.	KES (3)	2005	DBLP DOI BibTeX RDF
16	Malay K. Ganai, Aarti Gupta, Pranav Ashar	Beyond safety: customized SAT-based model checking.	DAC	2005	DBLP DOI BibTeX RDF	circuit cofactoring, unbounded model checking, formal verification, SAT, liveness, bounded model checking, LTL
16	Elisa Bertino, Barbara Carminati, Elena Ferrari, Bhavani Thuraisingham, Amar Gupta	Selective and Authentic Third-Party Distribution of XML Documents.	IEEE Trans. Knowl. Data Eng.	2004	DBLP DOI BibTeX RDF
16	Erzsébet Csuhaj-Varjú, Carlos Martín-Vide, Gheorghe Paun, Arto Salomaa	From Watson-Crick L systems to Darwinian P systems.	Nat. Comput.	2003	DBLP DOI BibTeX RDF	Watson-Crick complementarity, L system, membrane computing, P system, recursively enumerable language
16	Frank S. de Boer, Cees Pierik	How to Cook a Complete Hoare Logic for Your Pet OO Language.	FMCO	2003	DBLP DOI BibTeX RDF
16	Hyunseok Chang, Ramesh Govindan, Sugih Jamin, Scott Shenker, Walter Willinger	Towards capturing representative AS-level Internet topologies.	SIGMETRICS	2002	DBLP DOI BibTeX RDF
16	Patrick Blackburn, Maarten Marx	Tableaux for Quantified Hybrid Logic.	TABLEAUX	2002	DBLP DOI BibTeX RDF
16	Ben C. Moszkowski	A Complete Axiomatization of Interval Temporal Logic with Infinite Time.	LICS	2000	DBLP DOI BibTeX RDF	complete axiom systems, Buechi-automata, temporal logic, regular expressions, finite-state automata, omega-automata
16	Rostislav E. Yavorsky	On the Logic of the Standard Proof Predicate.	CSL	2000	DBLP DOI BibTeX RDF	logic of proofs, protocolling extensions of theories, semantics
16	Kenneth A. Kaufman, Ryszard S. Michalski	Learning from Inconsistent and Noisy Data: The AQ18 Approach.	ISMIS	1999	DBLP DOI BibTeX RDF
16	Mats Per Erik Heimdahl	Experiences and Lessons from the Analysis of TCAS II.	ISSTA	1996	DBLP DOI BibTeX RDF
16	Herman Geuvers	Extending Models of Second Order Predicate Logic to Models of Second Dependent Type Theory.	CSL	1996	DBLP DOI BibTeX RDF
16	Laurent Vigneron	Positive Deduction modulo Regular Theories.	CSL	1995	DBLP DOI BibTeX RDF
16	Vladislav Rutenburg	Complexity Classification of Truth Maintenance Systems.	STACS	1991	DBLP DOI BibTeX RDF
16	Harry Buhrman, Edith Spaan, Leen Torenvliet	Bounded Reductions.	STACS	1991	DBLP DOI BibTeX RDF
16	Wayne Snyder	Higher Order E-Unification.	CADE	1990	DBLP DOI BibTeX RDF
16	Leo Bachmair, Harald Ganzinger	On Restrictions of Ordered Paramodulation with Simplification.	CADE	1990	DBLP DOI BibTeX RDF
16	Roland N. Bol, Krzysztof R. Apt, Jan Willem Klop	On the Power of Subsumption and Context Checks.	DISCO	1990	DBLP DOI BibTeX RDF
16	Leo Bachmair	Proof Normalization for Resolution and Paramodulation.	RTA	1989	DBLP DOI BibTeX RDF
16	Elias Dahlhaus, Marek Karpinski	A Fast Parallel Algorithm for Computing all Maximal Cliques in a Graph and the Related Problems (Extended Abstract).	SWAT	1988	DBLP DOI BibTeX RDF
12	Philip W. L. Fong	Preventing Sybil Attacks by Privilege Attenuation: A Design Principle for Social Network Systems.	IEEE Symposium on Security and Privacy	2011	DBLP DOI BibTeX RDF	Principle of Privilege Attenuation, completeness of static analysis, access control, soundness, Sybil attacks, social network systems
12	Dominique Attali, André Lieutier	Optimal reconstruction might be hard.	SCG	2010	DBLP DOI BibTeX RDF	3SAT, homological simplification, sampling conditions, topological persistence, NP-completeness, shape reconstruction
12	Ramamohan Paturi, Pavel Pudlák	On the complexity of circuit satisfiability.	STOC	2010	DBLP DOI BibTeX RDF	NP-completeness, circuit satisfiability
12	Michael J. Fischer, Xueyuan Su, Yitong Yin	Assigning tasks for efficiency in Hadoop: extended abstract.	SPAA	2010	DBLP DOI BibTeX RDF	approximation algorithm, load balancing, np-completeness, mapreduce, hadoop, task assignment
12	Ladislav J. Kohout	Finite Complete Systems of Many-valued Logic Algebras.	Encyclopedia of Optimization	2009	DBLP DOI BibTeX RDF	PI-logic algebras, Discrete functions, Computational complexity, Satisfiability, Many-valued logics, Normal form, Medical applications, Scientific applications, Descriptive complexity, Functional completeness
12	Ricardo V. Oliveira, Beichuan Zhang 0001, Dan Pei, Lixia Zhang 0001	Quantifying path exploration in the internet.	IEEE/ACM Trans. Netw.	2009	DBLP DOI BibTeX RDF	AS topology completeness, border gateway protocol (BGP), internet topology, inter-domain routing
12	Sabyasachi Roy, Himabindu Pucha, Zheng Zhang 0009, Y. Charlie Hu, Lili Qiu	On the placement of infrastructure overlay nodes.	IEEE/ACM Trans. Netw.	2009	DBLP DOI BibTeX RDF	reliability, TCP, NP-completeness, TCP/IP, placement, overlay networks
12	Xi Chen 0001, Xiaotie Deng, Shang-Hua Teng	Settling the complexity of computing two-player Nash equilibria.	J. ACM	2009	DBLP DOI BibTeX RDF	Arrow-Debreu market, Brouwer's fixed point, Lemke-Howson algorithm, PPAD-completeness, Sperner's lemma, Nash equilibrium, smoothed analysis, Two-player game
12	Greg Restall	Truth Values and Proof Theory.	Stud Logica	2009	DBLP DOI BibTeX RDF	Completeness, Modal Logic, Proof, Sequent Calculus, Intuitionistic Logic, Truth Value
12	Martin Olsen	Nash Stability in Additively Separable Hedonic Games and Community Structures.	Theory Comput. Syst.	2009	DBLP DOI BibTeX RDF	Additively separable hedonic games, Nash stability, NP-completeness, Community structures
12	Mirko Malekovic, Mirko Cubrilo, Kornelije Rabuzin	Logical Consequences in Partial Knowledge Bases.	Towards Intelligent Engineering and Information Technology	2009	DBLP DOI BibTeX RDF	partial knowledge bases, dependencies, completeness, soundness, inference rules, formal systems, logical consequences
12	Trac N. Nguyen, Dung T. Huynh	Minimum Interference Planar Geometric Topology in Wireless Sensor Networks.	WASA	2009	DBLP DOI BibTeX RDF	planar topology, Wireless sensor networks, NP-completeness, interference, geometric graphs
12	Scott Heard, Jing Huang	Kernel-Perfection through the Push Operation.	NCM	2009	DBLP DOI BibTeX RDF	kernel-perfection, the push operation, NP-completeness, Kernel
12	Xi Chen 0001, Decheng Dai, Ye Du, Shang-Hua Teng	Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities.	FOCS	2009	DBLP DOI BibTeX RDF	Arrow-Debreu markets, PPAD-completeness, Computational complexity
12	Matteo Magnani, Danilo Montesi	Towards Relational Schema Uncertainty.	SUM	2009	DBLP DOI BibTeX RDF	uncertainty, completeness, soundness, schema, possible worlds
12	Johannes Köbler, Sebastian Kuhnert	The Isomorphism Problem for k-Trees Is Complete for Logspace.	MFCS	2009	DBLP DOI BibTeX RDF	graph canonization, logspace completeness, graph isomorphism, space complexity, k-trees
12	Marc Pouzet, Pascal Raymond	Modular static scheduling of synchronous data-flow networks: an efficient symbolic representation.	EMSOFT	2009	DBLP DOI BibTeX RDF	real-time systems, compilation, semantics, np-completeness, partial orders, synchronous languages, block-diagrams, preorders
12	Stefan Porschen, Tatjana Schmidt, Ewald Speckenmeyer	On Some Aspects of Mixed Horn Formulas.	SAT	2009	DBLP DOI BibTeX RDF	Mixed Horn formula, polynomial time reduction, NP-completeness, satisfiability, exact algorithm
12	Shengli Zhang, Zhenghua Pan	One New Interpretation of Infinite Valued for Medium Proposition Logic.	FSKD (6)	2009	DBLP DOI BibTeX RDF	medium proposition logic, three-valued model, infinite-valued model, completeness and soundness
12	Renata P. de Freitas, Sheila R. M. Veloso, Paulo A. S. Veloso, Jorge Petrucio Viana	Positive Fork Graph Calculus.	LFCS	2009	DBLP DOI BibTeX RDF	Positive relational calculi, fork algebras, graph calculus, completeness, decidability
12	Jakub Kovác, Tomás Vinar, Brona Brejová	Predicting Gene Structures from Multiple RT-PCR Tests.	WABI	2009	DBLP DOI BibTeX RDF	RT-PCR, splicing graph, dynamic programming, NP-completeness, gene finding
12	Jan Lunze	Fault Diagnosis of Discretely Controlled Continuous Systems by Means of Discrete-Event Models.	Discret. Event Dyn. Syst.	2008	DBLP DOI BibTeX RDF	Embedded map, Nondeterministic automaton, Fault diagnosis, Hybrid system, Completeness, Semi-Markov process, Timed automaton, Model abstraction
12	Chun-Yuan Chiu, Yu-Liang Kuo, Eric Hsiao-Kuang Wu, Gen-Huey Chen	Bandwidth-Constrained Routing Problem in Wireless Ad Hoc Networks.	IEEE Trans. Parallel Distributed Syst.	2008	DBLP DOI BibTeX RDF	reducibility and completeness, routing protocols, Algorithm/protocol design and analysis, mobile communication systems
12	Tomasz Jurdzinski, Friedrich Otto, Frantisek Mráz, Martin Plátek	On the Complexity of 2-Monotone Restarting Automata.	Theory Comput. Syst.	2008	DBLP DOI BibTeX RDF	Restarting automaton, Growing context-sensitive language, completeness, Monotonicity
12	Lucian Leahu, Phoebe Sengers, Michael Mateas	Interactionist AI and the promise of ubicomp, or, how to put your box in the world without putting the world in your box.	UbiComp	2008	DBLP DOI BibTeX RDF	AI-completeness, interactionist AI, reflective HCI
12	Renata P. de Freitas, Paulo A. S. Veloso, Sheila R. M. Veloso, Jorge Petrucio Viana	On a Graph Calculus for Algebras of Relations.	WoLLIC	2008	DBLP DOI BibTeX RDF	Relational language, reasoning from hypotheses, graph calculus, completeness, complementation
12	Radim Belohlávek, Vilém Vychodil	Adding background knowledge to formal concept analysis via attribute dependency formulas.	SAC	2008	DBLP DOI BibTeX RDF	attribute dependencies, completeness, formal concept analysis, background knowledge, entailment
12	Hugo Herbelin, Silvia Ghilezan	An approach to call-by-name delimited continuations.	POPL	2008	DBLP DOI BibTeX RDF	boehm separability, delimited control, observational completeness, classical logic
12	Yan Gérard	Reconstructing a Matrix with a Given List of Coefficients and Prescribed Row and Column Sums Is NP-Hard.	IWCIA	2008	DBLP DOI BibTeX RDF	combinatorial matrix theory, NP-completeness, discrete tomography
12	Zhiyao Liang, Rakesh M. Verma	Complexity of Checking Freshness of Cryptographic Protocols.	ICISS	2008	DBLP DOI BibTeX RDF	Athena, NP-completeness, Cryptographic protocols, undecidability, replay attack, model checker, freshness, challenge response
12	Manuel Rubio-Sánchez	An introduction to problem equivalence with combinatorics.	ITiCSE	2008	DBLP DOI BibTeX RDF	problem equivalence, NP-completeness, recursion, combinatorics, counting problems, fibonacci numbers
12	Yalin Zheng, Guang Yang 0002, Changshui Zhang, Jing Zheng, Yunpeng Xu	Equivalence Knowledge Mass and Approximate Reasoning in -Logic (I).	ICIC (2)	2008	DBLP DOI BibTeX RDF	Knowledge Cumularspharolith, Formulae Cumularspharolith, Approximate Knowledge Closure of Knowledge Base, Pseudo-distance, automatic Reasoning System, completeness
12	Guoxing Zhao, Jixin Ma 0001, Fuxing Shen, Miltos Petridis	A Sound and Complete Reified Temporal Logic.	SNPD	2008	DBLP DOI BibTeX RDF	Reified Temporal Logic, Completeness
12	Tetsuo Yokoyama, Holger Bock Axelsen, Robert Glück	Principles of a reversible programming language.	Conf. Computing Frontiers	2008	DBLP DOI BibTeX RDF	backward determinism, inverse semantics, fast fourier transform, reversible computing, turing completeness
12	Rémy Malgouyres, Angel R. Francés	Determining Whether a Simplicial 3-Complex Collapses to a 1-Complex Is NP-Complete.	DGCI	2008	DBLP DOI BibTeX RDF	Simplicial Topology, NP??completeness, Computational Complexity, Collapsing
12	Ariadi Nugroho, Michel R. V. Chaudron	A survey into the rigor of UML use and its perceived impact on quality and productivity.	ESEM	2008	DBLP DOI BibTeX RDF	unified modeling language, consistency, level of detail, completeness, correspondence
12	Zoran Nikoloski, Sergio Grimbs, Joachim Selbig, Oliver Ebenhöh	Hardness and Approximability of the Inverse Scope Problem.	WABI	2008	DBLP DOI BibTeX RDF	completeness, scope, metabolic networks
12	Arvind Gupta, Pavol Hell, Mehdi Karimi 0001, Arash Rafiey	Minimum Cost Homomorphisms to Reflexive Digraphs.	LATIN	2008	DBLP DOI BibTeX RDF	minimum cost homomorphism, reflexive digraph, NP-completeness, polynomial time algorithm, homomorphism, dichotomy
12	Oliver Kutz	Notes on Logics of Metric Spaces.	Stud Logica	2007	DBLP DOI BibTeX RDF	expressive completeness, Boolean modal logic, interpolation, Metric spaces, hybrid logic, axiomatisation
12	Subhashis Majumder, Susmita Sur-Kolay, Bhargab B. Bhattacharya, Swarup Kumar Das	Hierarchical partitioning of VLSI floorplans by staircases.	ACM Trans. Design Autom. Electr. Syst.	2007	DBLP DOI BibTeX RDF	balanced bipartitioning, NP-completeness, Floorplanning, network flow, global routing
12	Morteza Moniri	Preservation theorems for bounded formulas.	Arch. Math. Log.	2007	DBLP DOI BibTeX RDF	Polynomial induction, Model completeness, Universal theory, Quantifier elimination, Intuitionistic logic, NP, Bounded arithmetic, Polynomial hierarchy, Kripke model
12	Carlos Ordonez 0001, Javier García-García 0001, Zhibo Chen 0002	Measuring referential integrity in distributed databases.	CIMS	2007	DBLP DOI BibTeX RDF	database, metric, consistency, completeness
12	Hovav Shacham	The geometry of innocent flesh on the bone: return-into-libc without function calls (on the x86).	CCS	2007	DBLP DOI BibTeX RDF	return-into-libc, instruction set, turing completeness
12	Shin-Ichi Nakano, Ryuhei Uehara, Takeaki Uno	Efficient Algorithms for Airline Problem.	TAMC	2007	DBLP DOI BibTeX RDF	Airline problem, approximation algorithm, completeness, efficient algorithm
12	Luis Rademacher	Approximating the centroid is hard.	SCG	2007	DBLP DOI BibTeX RDF	approximation, completeness, centroid, hardness, convex body
12	Artiom Alhazov, Rudolf Freund, Marion Oswald, Sergey Verlan	Partial Halting in P Systems Using Membrane Rules with Permitting Contexts.	MCU	2007	DBLP DOI BibTeX RDF	computational completeness, halting, minimal parallelism, permitting context, P systems
12	Peter Schuster 0001	Problems as Solutions.	CiE	2007	DBLP DOI BibTeX RDF	uniform continuity, unique existence, countable choice, completeness, Metric spaces, constructive mathematics
12	Martin Olsen	Nash Stability in Additively Separable Hedonic Games Is NP-Hard.	CiE	2007	DBLP DOI BibTeX RDF	Nash Stability, Hedonic Games, NP-Completeness
12	Susanne Albers, Fabian Müller, Swen Schmelzer	Speed scaling on parallel processors.	SPAA	2007	DBLP DOI BibTeX RDF	approximation algorithms, energy efficiency, NP-completeness, online algorithms, multiprocessor scheduling
12	Vladimir Lifschitz, Alexander A. Razborov	Why are there so many loop formulas?	ACM Trans. Comput. Log.	2006	DBLP DOI BibTeX RDF	loop formulas, stable models, P-completeness, Answer sets