Search results for "np-completeness"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
101	Klaus Ambos-Spies, Levke Bentzien	Separating NP-Completeness Notions under Strong Hypotheses.	CCC	1997	DBLP DOI BibTeX RDF	NP-completeness notions separation, strong hypotheses, NP-m-completeness, NP-T-completeness, bounded-query reducibilities, resource bounded Baire category concept, computational complexity, resource bounded measure
95	Daniel Leivant	On the Completeness of Dynamic Logic.	FoSSaCS	2009	DBLP DOI BibTeX RDF	inductive completeness, relative completeness, arithmetical completeness, Dynamic logic
93	S. Karunanithi, Arthur D. Friedman	Some New Types of Logical Completeness.	IEEE Trans. Computers	1978	DBLP DOI BibTeX RDF	weak completeness, Combinational functions, complement completeness, dual completeness, logic primitives, necessary and sufficient conditions for c-completeness, strong c-completeness, weak c-completeness, strong completeness
88	Zhenghua Pan	Relation between Semantic Completeness and Syntax Completeness on General Formal Systems.	SKG	2006	DBLP DOI BibTeX RDF
73	Klaus Ambos-Spies, Elvira Mayordomo, Xizhong Zheng	A Comparison of Weak Completeness Notions.	CCC	1996	DBLP DOI BibTeX RDF	Weak Completeness, Measure, Genericity, Completeness
57	Alioune Ngom, Corina Reischer, Dan A. Simovici, Ivan Stojmenovic	Completeness Criteria in Set-Valued Logic Under Compositions with Union and Intersection.	ISMVL	1997	DBLP DOI BibTeX RDF	completeness criteria, set-valued logic, Boolean completeness problems, r-valued set logic, logic of functions, n-tuples, set logic circuits, S-complete, U-maximal sets, completeness criterion, U functions, compositions, Boolean functions, Boolean functions, intersection, union
56	Jens Knoop, Oliver Rüthing	Optimization Under the Perspective of Soundness, Completeness, and Reusability.	Correct System Design	1999	DBLP DOI BibTeX RDF	Programming paradigms (imperative, explicitly parallel, object-oriented), safety and coincidence theorems, optimizer generators, optimality, completeness, data-flow analysis, reusability, soundness, program optimization, code motion, admissibility
55	Yuan Lin 0005, Richard C. Holt, Andrew J. Malton	Completeness of a Fact Extractor.	WCRE	2003	DBLP DOI BibTeX RDF
51	John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran	Partial Bi-immunity, Scaled Dimension, and NP-Completeness.	Theory Comput. Syst.	2008	DBLP DOI BibTeX RDF	Many-one completeness, Bi-immunity, Scaled dimension, Turing completeness
50	Mila Dalla Preda	Completeness Refinement in Abstract Symbolic Trajectory Evaluation.	SAS	2004	DBLP DOI BibTeX RDF	Domain Refinement, Model-checking, Verification, Abstract Interpretation, Completeness, Data Flow Analysis, Symbolic Trajectory Evaluation
50	Reiner Hähnle, Neil V. Murray, Erik Rosenthal	Completeness for Linear Regular Negation Normal Form Inference Systems.	ISMIS	1997	DBLP DOI BibTeX RDF	tableau method, non-clausal inference, negation normal form, completeness, resolution, Logic for Artificial Intelligence
50	Roberto Giacobazzi, Elisa Quintarelli	Incompleteness, Counterexamples, and Refinements in Abstract Model-Checking.	SAS	2001	DBLP DOI BibTeX RDF	Domain Refinement, Model-checking, Verification, Program Analysis, Abstract Interpretation, Completeness
49	Tauqeer Hussain, Mian M. Awais	An Effort-Based Approach to Measure Completeness of an Entity-Relationship Model.	ACIS-ICIS	2008	DBLP DOI BibTeX RDF
49	Reinhard Pichler	Completeness and Redundancy in Constrained Clause Logic.	FTP (LNCS Selection)	1998	DBLP DOI BibTeX RDF
49	Daniel Leivant, Tim Fernando	Skinny and Fleshy Failures of Relative Completeness.	POPL	1987	DBLP DOI BibTeX RDF
45	Boris A. Romov	Completeness Theory for Vector Partial Multiple-Valued Logic Functions.	ISMVL	1995	DBLP DOI BibTeX RDF	completeness theory, vector partial multiple-valued logic functions, completeness criterion, multiple-base invariant relations algebra, restricted quantifier free calculus, multivalued logic, Galois connection
45	Adel Bouhoula	Simultaneous checking of completeness and ground confluence for algebraic specifications.	ACM Trans. Comput. Log.	2009	DBLP DOI BibTeX RDF	ground confluence, completeness, algebraic specifications, parameterization, term rewriting systems, Automated deduction
45	Donald P. Ballou, Harold L. Pazer	Modeling Completeness versus Consistency Tradeoffs in Information Decision Contexts.	IEEE Trans. Knowl. Data Eng.	2003	DBLP DOI BibTeX RDF	tradeoffs for data quality, consistency, decision making, Completeness, data quality
45	James Clifford, Albert Croker, Alexander Tuzhilin	On Completeness of Historical Relational Query Languages.	ACM Trans. Database Syst.	1994	DBLP DOI BibTeX RDF	temporal grouping, temporal logic, query languages, completeness, temporal databases, relational model, historical databases
45	Deepak Kapur, Paliath Narendran, Hantao Zhang 0001	Complexity of Sufficient-Completeness.	FSTTCS	1986	DBLP DOI BibTeX RDF	normal forms, term rewriting systems, PSPACE, Sufficient-completeness
44	Rotem Oshman	An Automata-Theoretic Dynamic Completeness Criterion for Bounded Model-Checking.	VMCAI	2009	DBLP DOI BibTeX RDF
44	Joe Hendrix, José Meseguer 0001	On the Completeness of Context-Sensitive Order-Sorted Specifications.	RTA	2007	DBLP DOI BibTeX RDF
44	Aart Middeldorp, Yoshihito Toyama	Completeness of Combinations of Constructor Systems.	RTA	1991	DBLP DOI BibTeX RDF
44	François Bancilhon	On the Completeness of Query Languages for Relational Data Bases.	MFCS	1978	DBLP DOI BibTeX RDF
39	Francesc Esteva, Lluís Godo, Carles Noguera	Expanding the propositional logic of a t-norm with truth-constants: completeness results for rational semantics.	Soft Comput.	2010	DBLP DOI BibTeX RDF	Mathematical fuzzy logic, Left-continuous t-norms, T-norm based logics, Truth-constants, Evaluated formulae, Real and rational completeness
39	Omer Horvitz, Virgil D. Gligor	Weak Key Authenticity and the Computational Completeness of Formal Encryption.	CRYPTO	2003	DBLP DOI BibTeX RDF	Weak Key Authenticity, Authentication, Cryptography, Encryption, Completeness, Formal Reasoning
38	Michele Basaldella, Kazushige Terui	On the Meaning of Logical Completeness.	TLCA	2009	DBLP DOI BibTeX RDF
38	Venkatesan Guruswami	On 2-Query Codeword Testing with Near-Perfect Completeness.	ISAAC	2006	DBLP DOI BibTeX RDF
38	David A. Schmidt	Comparing Completeness Properties of Static Analyses and Their Logics.	APLAS	2006	DBLP DOI BibTeX RDF
38	Jit Biswas, Felix Naumann, Qiang Qiu	Assessing the Completeness of Sensor Data.	DASFAA	2006	DBLP DOI BibTeX RDF
38	Tauqeer Hussain, Mian M. Awais, Shafay Shamail	A Fuzzy Based Approach to Measure Completeness of an Entity-Relationship Model.	ER (Workshops)	2005	DBLP DOI BibTeX RDF
38	Satoshi Okui, Aart Middeldorp, Tetsuo Ida	Lazy Narrowing: Strong Completeness and Eager Variable Elimination (Extended Abstract).	TAPSOFT	1995	DBLP DOI BibTeX RDF
38	Edgar Knapp	Soundness and Completeness of UNITY Logic.	FSTTCS	1994	DBLP DOI BibTeX RDF	Classification Theory of Programming Languages, Logic in Computer Science, Theory of Parallel and Distributed Computation
34	Xiaodan Chen, Shaobai Chen	On the Upper Completeness of Quasi-metric Spaces.	IITSI	2010	DBLP DOI BibTeX RDF	Quasi-metric space, upper limit, upper closed set, Yoneda-completeness, upper completeness
34	Yoshio Okamoto, Takeaki Uno, Ryuhei Uehara	Linear-Time Counting Algorithms for Independent Sets in Chordal Graphs.	WG	2005	DBLP DOI BibTeX RDF	# P-completeness, NP-completeness, polynomial time algorithm, enumeration, independent set, Chordal graph, counting
34	Pierluigi Crescenzi	Using AVs to explain NP-completeness.	ITiCSE	2010	DBLP DOI BibTeX RDF	NP-completeness, algorithm visualization
34	Fabian Panse, Norbert Ritter	Completeness in Databases with Maybe-Tuples.	ER Workshops	2009	DBLP DOI BibTeX RDF	data completeness, maybe tuple, probabilistic database
34	Gerard R. Renardel de Lavalette, Barteld P. Kooi, Rineke Verbrugge	Strong Completeness and Limited Canonicity for PDL.	J. Log. Lang. Inf.	2008	DBLP DOI BibTeX RDF	Canonical model, Model disharmony, Propositional dynamic logic, Strong completeness
34	Marcel Karnstedt, Kai-Uwe Sattler, Michael Haß, Manfred Hauswirth, Brahmananda Sapkota, Roman Schmidt	Approximating query completeness by predicting the number of answers in DHT-based web applications.	WIDM	2008	DBLP DOI BibTeX RDF	query completeness, query processing, dht, probabilistic guarantees
34	Gilberto A. Cysneiros Filho, Andrea Zisman	Traceability and completeness checking for agent-oriented systems.	SAC	2008	DBLP DOI BibTeX RDF	completeness checking, multi-agent systems, traceability, agent oriented software engineering
34	Lian Yu, Shuang Su, Shan Luo, Yu Su 0007	Completeness and Consistency Analysis on Requirements of Distributed Event-Driven Systems.	TASE	2008	DBLP DOI BibTeX RDF	Completeness and consistency analysis, requirement-related faults, formal scenario model, inconsistency elimination, event-driven systems
34	Mark Burgin	Universality, Reducibility, and Completeness.	MCU	2007	DBLP DOI BibTeX RDF	problem completeness, algorithm, computability, reducibility, universal, computing power, problem hardness
34	David S. Johnson	The NP-completeness column.	ACM Trans. Algorithms	2005	DBLP DOI BibTeX RDF	lattice bases, NP-completeness, coding theory, perfect graphs, primality testing, open problems
34	Radosav S. Dordevic, Miodrag Raskovic, Zoran Ognjanovic	Completeness theorem for propositional probabilistic models whose measures have only finite ranges.	Arch. Math. Log.	2004	DBLP DOI BibTeX RDF	Finite ranges of probabilities, Completeness, Probabilistic logic
34	Amit M. Paradkar, Tim Klinger	Automated Consistency and Completeness Checking of Testing Models for Interactive Systems.	COMPSAC	2004	DBLP DOI BibTeX RDF	Completeness Checking, Reachability, Consistency Checking
34	Naijun Zhan	Completeness of Higher-Order Duration Calculus.	CSL	2000	DBLP DOI BibTeX RDF	duration calculus higher-order logic interval temporal logic completeness
34	Wolfgang Bibel, Elmar Eder	Decomposition of tautologies into regular formulas and strong completeness of connection-graph resolution.	J. ACM	1997	DBLP DOI BibTeX RDF	connection-graph resolution, decomposition of unsatisfiable formulas, semantic trees, regular graphs, strong completeness
34	Adel Bouhoula	Sufficient Completeness and Parameterized Proofs by Induction.	ALP	1994	DBLP DOI BibTeX RDF	Implicit induction, Parameterized Conditional Specifications, Theorem Proving, Term rewriting systems, Sufficient completeness
34	Jan A. Plaza	Completeness for Propositional Logic Programs with Negation.	ISMIS	1991	DBLP DOI BibTeX RDF	SLD-resolution, knowledge representation in logic, logic programming, declarative programming, constructive negation, rule-based expert systems, non-classical logics, negation as failure, soundness and completeness
34	Michael R. Hansen, Zhou Chaochen	Semantics and Completeness of Duration Calculus.	REX Workshop	1991	DBLP DOI BibTeX RDF	relative completeness, real-time systems, verification, specifications, specification languages, proof system, Duration Calculus, Interval Temporal Logic
34	Michael Merritt	Completeness Theorems for Automata.	REX Workshop	1989	DBLP DOI BibTeX RDF	state mappings, Specification, implementation, products, completeness, automata
34	Pieter J. Collins, C. A. Hendrie	On Strict Extensions of Nearness Spaces.	Appl. Categorical Struct.	2000	DBLP DOI BibTeX RDF	T-uniformity, nearness space, round Cauchy filter, strict extension, completeness
33	Antonio Caruso 0001, Stefano Chessa, Piero Maestrini	Worst-Case Diagnosis Completeness in Regular Graphs under the PMC Model.	IEEE Trans. Computers	2007	DBLP DOI BibTeX RDF	isoperimeter, Fault tolerance, Graph Theory, parallel architectures, fault diagnosis, system-level diagnosis
33	Zhongnan Shen, Jianwen Su	On Completeness of Web Service Compositions.	ICWS	2007	DBLP DOI BibTeX RDF
33	Marius Petria	An Institutional Version of Gödel's Completeness Theorem.	CALCO	2007	DBLP DOI BibTeX RDF
33	M. Kathryn Brohman, Richard T. Watson, Gabriele Piccoli, A. Parasuraman	NCSS Process Completeness: Construct Development and Preliminary Validation.	HICSS	2005	DBLP DOI BibTeX RDF
33	Joe Hendrix, Manuel Clavel, José Meseguer 0001	A Sufficient Completeness Reasoning Tool for Partial Specifications.	RTA	2005	DBLP DOI BibTeX RDF
33	Lars Engebretsen, Jonas Holmerin	Three-Query PCPs with Perfect Completeness over non-Boolean Domains.	CCC	2003	DBLP DOI BibTeX RDF
33	Wlodzimierz Drabent, Miroslawa Milkowska	Proving Correctness and Completeness of Normal Programs - A Declarative Approach.	ICLP	2001	DBLP DOI BibTeX RDF
33	Holger Spakowski, Jörg Vogel 0001	Theta2p-Completeness: A Classical Approach for New Results.	FSTTCS	2000	DBLP DOI BibTeX RDF
33	M. R. K. Krishna Rao	Semi-Completeness of Hierarchical and Super-Hierarchical Combinations of Term Rewriting Systems.	TAPSOFT	1995	DBLP DOI BibTeX RDF
33	Aart Middeldorp, Erik Hamoen	Counterexamples to Completeness Results for Basic Narrowing (Extended Abstract).	ALP	1992	DBLP DOI BibTeX RDF
33	Andreas Goerdt	Hoare Calculi for Higher-Type Control Structures and Their Completeness in the Sense of Cook.	MFCS	1988	DBLP DOI BibTeX RDF
33	David Harel	Arithmetical Completeness in Logics of Programs.	ICALP	1978	DBLP DOI BibTeX RDF
33	Robert Anderson, W. W. Bledsoe	A Linear Format for Resolution With Merging and a New Technique for Establishing Completeness.	J. ACM	1970	DBLP DOI BibTeX RDF
33	Isabella Mastroeni	Deriving Bisimulations by Simplifying Partitions.	VMCAI	2008	DBLP DOI BibTeX RDF
33	Roberto Giacobazzi, Francesco Ranzato, Francesca Scozzari	Making abstract interpretations complete.	J. ACM	2000	DBLP DOI BibTeX RDF
33	Rob J. van Glabbeek	Axiomatizing Flat Iteration.	CONCUR	1997	DBLP DOI BibTeX RDF
33	V. S. Subrahmanian	Query Processing in Quantitative Logic Programming.	CADE	1988	DBLP DOI BibTeX RDF
28	Wenfei Fan, Floris Geerts	Relative information completeness.	PODS	2009	DBLP DOI BibTeX RDF	information completeness, master data, constraints, consistency
28	Philippe Balbiani	Axiomatization and Completeness of Lexicographic Products of Modal Logics.	FroCoS	2009	DBLP DOI BibTeX RDF	lexicographic product, axiomatization/completeness, Modal logic
28	Tommaso Flaminio	Strong non-standard completeness for fuzzy logics.	Soft Comput.	2008	DBLP DOI BibTeX RDF	Non-standard completeness, Ultraproduct construction, Fuzzy events, Conditional probability
28	Van Hung Le 0001, Fei Liu 0003, Dinh Khang Tran	Fixpoint Semantics and Completeness of the Computational Model for Fuzzy Linguistic Logic Programming.	ICIC (2)	2008	DBLP DOI BibTeX RDF	hedge algebra, linguistic value, completeness, fuzzy logic programming, fixpoint semantics, linguistic hedge
28	Jan Kodovský, Jessica J. Fridrich	On completeness of feature spaces in blind steganalysis.	MM&Sec	2008	DBLP DOI BibTeX RDF	fcm, steganography, completeness, blind steganalysis
28	Torben Braüner	Proof-Theoretic Functional Completeness for the Hybrid Logics of Everywhere and Elsewhere.	Stud Logica	2005	DBLP DOI BibTeX RDF	Modal logic, hybrid logic, natural deduction, functional completeness
28	Rana Barua	Completeness of a combination of neighbourhood logic and temporal logic.	Formal Aspects Comput.	2004	DBLP DOI BibTeX RDF	Neighbourhood logic, Completeness, Possible world semantics, Interval logic, First-order temporal logic
28	Danny Harnik, Moni Naor, Omer Reingold, Alon Rosen	Completeness in two-party secure computation: a computational view.	STOC	2004	DBLP DOI BibTeX RDF	oblivious tansfer, completeness, secure computation
28	Xiuzhen Cheng 0001, Bhagirath Narahari, Rahul Simha, Maggie Xiaoyan Cheng, Dan Liu	Strong Minimum Energy Topology in Wireless Sensor Networks: NP-Completeness and Heuristics.	IEEE Trans. Mob. Comput.	2003	DBLP DOI BibTeX RDF	Minimum energy topology, incremental power heuristic, wireless sensor networks, NP-Completeness, power control
28	Alexander L. Chistov, Hervé Fournier, Leonid Gurvits, Pascal Koiran	Vandermonde Matrices, NP-Completeness, and Transversal Subspaces.	Found. Comput. Math.	2003	DBLP DOI BibTeX RDF	Vandermonde Matrices, Transversal Subspaces, NP-Completeness
28	Grigori Mints, Darko Sarenac	Completeness of indexed epsilon-calculus.	Arch. Math. Log.	2003	DBLP DOI BibTeX RDF	Epsilon calculus, Finite choice, Completeness
28	Nancy G. Leveson	Completeness in formal specification language design for process-control systems.	FMSP	2000	DBLP DOI BibTeX RDF	completeness, process-control, Formal specification language
28	James Laird	Finite Models and Full Completeness.	CSL	2000	DBLP DOI BibTeX RDF	affine logic, full completeness, effective presentability, linear logic, PCF
28	Jack Jie Dai, Jack H. Lutz	Query Order and NP-Completeness.	CCC	1999	DBLP DOI BibTeX RDF	query order, resource-bounded genericity, computational complexity, NP-completeness, complexity classes, resource-bounded measure
28	Jan Van den Bussche, Dirk Van Gucht, Marc Andries, Marc Gyssens	On the completeness of object-creating database transformation languages.	J. ACM	1997	DBLP DOI BibTeX RDF	computational completeness, constructive transformation, while loop, object-oriented database, first-order logic, object creation
28	Mats Per Erik Heimdahl, Nancy G. Leveson	Completeness and Consistency in Hierarchical State-Based Requirements.	IEEE Trans. Software Eng.	1996	DBLP DOI BibTeX RDF	state-based requirements, formal methods, static analysis, consistency, Completeness, reactive systems, formal semantics
28	Mats Per Erik Heimdahl, Barbara J. Czerny	Using PVS to analyze hierarchical state-based requirements for completeness and consistency.	HASE	1996	DBLP DOI BibTeX RDF	hierarchical state based requirements specifications, input sequence, analysis procedures, large real world requirements specification, hierarchical state based language, Requirements State Machine Language, Prototype Verification System, theorem proving component, spurious error reports, formal specifications, robustness, consistency, program verification, completeness, Binary Decision Diagrams, BDDs, PVS, interactive environment, formal proofs, RSML
28	Boris A. Romov	Polynomial Completeness Criteria in Finite Boolean Algebras.	ISMVL	1996	DBLP DOI BibTeX RDF	completeness criteria, finite Boolean algebras, arity-calibrated product, two-valued logic algebras, maximal subalgebras, Sheffer criterion, Slupecki type criterion, multiple base relation, logic algebras, process algebra, polynomials, algebra, Boolean algebra
28	Pankaj Jalote	Testing the Completeness of Specifications.	IEEE Trans. Software Eng.	1989	DBLP DOI BibTeX RDF	completeness testing, VAX system, data structures, Unix, program testing, conformance testing, abstract data types, test cases, axiomatic specifications
28	Donald A. Varvel, Leonard D. Shapiro	The Computational Completeness of Extended Database Query Languages.	IEEE Trans. Software Eng.	1989	DBLP DOI BibTeX RDF	computational completeness, extended database query languages, POSTGRES, GENESIS, Turing machine interpreter, traditional database languages, programming language, database management systems, query languages, computational power
28	Sergei G. Vorobyov	A structural completeness theorem for a class of conditional rewrite rule systems.	Conference on Computer Logic	1988	DBLP DOI BibTeX RDF	conditional rewrite rules, case splitting, finite termination, reduction, inference rules, confluency, proof search, decision algorithms, strong completeness
28	Alexander Krassovitskiy, Yurii Rogozhin, Sergey Verlan	Further Results on Insertion-Deletion Systems with One-Sided Contexts.	LATA	2008	DBLP DOI BibTeX RDF	Insertion-deletion systems, computational non-completeness, universality
28	Roberto Giacobazzi, Isabella Mastroeni	Adjoining Declassification and Attack Models by Abstract Interpretation.	ESOP	2005	DBLP DOI BibTeX RDF	abstract non-interference, Abstract interpretation, completeness, language-based security, declassification, adjunction, attack models
28	Lothar Rogge	Call Completeness Implies Completeness in the n -period Model of a Financial Market.	Finance Stochastics	2006	DBLP DOI BibTeX RDF	JEL Classifications C60, G10
28	Roald Lengu, Paolo Missier, Alvaro A. A. Fernandes, Giovanna Guerrini, Marco Mesiti	Time-completeness trade-offs in record linkage using adaptive query processing.	EDBT	2009	DBLP DOI BibTeX RDF
28	Dikran Dikranjan, Elena Martín Peinador, Vaja Tarieladze	Conway's Question: The Chase for Completeness.	Appl. Categorical Struct.	2007	DBLP DOI BibTeX RDF	Mathematics Subject Classifications (2000) Primary 22A05, 22B05, 54D25, 54H11, Secondary 54A35, 54D30, 54H13, 54B30
28	Kohei Honda 0001, Martin Berger 0001, Nobuko Yoshida	Descriptive and Relative Completeness of Logics for Higher-Order Functions.	ICALP (2)	2006	DBLP DOI BibTeX RDF
28	Leslie G. Valiant	Completeness for Parity Problems.	COCOON	2005	DBLP DOI BibTeX RDF
28	Mircea Marin, Aart Middeldorp	New completeness results for lazy conditional narrowing.	PPDP	2004	DBLP DOI BibTeX RDF	conditional rewriting, narrowing, evaluation strategies
28	Mohamed G. Gouda, Alex X. Liu	Firewall Design: Consistency, Completeness, and Compactness.	ICDCS	2004	DBLP DOI BibTeX RDF
28	Miquel Bofill, Albert Rubio	Well-Foundedness Is Sufficient for Completeness of Ordered Paramodulation.	CADE	2002	DBLP DOI BibTeX RDF