Stop the war!
Остановите войну!
for scientists:
default search action
Search dblp for Publications
export results for "p-completeness theory"
@incollection{DBLP:books/acm/23/Papadimitriou23, author = {Christos H. Papadimitriou}, editor = {Bruce M. Kapron}, title = {Cook's NP-completeness Paper and the Dawn of the New Theory}, booktitle = {Logic, Automata, and Computational Complexity: The Works of Stephen A. Cook}, series = {{ACM} Books}, volume = {43}, pages = {73--82}, publisher = {{ACM}}, year = {2023}, url = {https://doi.org/10.1145/3588287.3588292}, doi = {10.1145/3588287.3588292}, timestamp = {Thu, 21 Sep 2023 14:31:10 +0200}, biburl = {https://dblp.org/rec/books/acm/23/Papadimitriou23.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/jar/BonacinaGS20, author = {Maria Paola Bonacina and St{\'{e}}phane Graham{-}Lengrand and Natarajan Shankar}, title = {Conflict-Driven Satisfiability for Theory Combination: Transition System and Completeness}, journal = {J. Autom. Reason.}, volume = {64}, number = {3}, pages = {579--609}, year = {2020}, url = {https://doi.org/10.1007/s10817-018-09510-y}, doi = {10.1007/S10817-018-09510-Y}, timestamp = {Wed, 02 Sep 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/jar/BonacinaGS20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/jais/ReckerG19, author = {Jan Recker and Peter F. Green}, title = {How do Individuals Interpret Multiple Conceptual Models? {A} Theory of Combined Ontological Completeness and Overlap}, journal = {J. Assoc. Inf. Syst.}, volume = {20}, number = {8}, pages = {1}, year = {2019}, url = {https://aisel.aisnet.org/jais/vol20/iss8/1}, timestamp = {Thu, 14 May 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/jais/ReckerG19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/ijicot/CayrelDG17, author = {Pierre{-}Louis Cayrel and Mbouye Khady Diagne and Cheikh Thi{\'{e}}coumba Gueye}, title = {NP-completeness of the Goppa parameterised random binary quasi-dyadic syndrome decoding problem}, journal = {Int. J. Inf. Coding Theory}, volume = {4}, number = {4}, pages = {276--288}, year = {2017}, url = {https://doi.org/10.1504/IJICOT.2017.10005835}, doi = {10.1504/IJICOT.2017.10005835}, timestamp = {Thu, 24 Sep 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/ijicot/CayrelDG17.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/toct/Hrubes16, author = {Pavel Hrubes}, title = {On Hardness of Multilinearization and VNP-Completeness in Characteristic 2}, journal = {{ACM} Trans. Comput. Theory}, volume = {9}, number = {1}, pages = {1:1--1:14}, year = {2016}, url = {https://doi.org/10.1145/2940323}, doi = {10.1145/2940323}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/toct/Hrubes16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/mst/PourabdollahB15, author = {Amir Pourabdollah and Tim J. Brailsford}, title = {On the Turing Completeness of the Semantic Web}, journal = {Theory Comput. Syst.}, volume = {56}, number = {2}, pages = {291--308}, year = {2015}, url = {https://doi.org/10.1007/s00224-014-9536-x}, doi = {10.1007/S00224-014-9536-X}, timestamp = {Sun, 28 May 2017 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/mst/PourabdollahB15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/jphil/ArecesBHM14, author = {Carlos Areces and Patrick Blackburn and Antonia Huertas and Mar{\'{\i}}a Manzano}, title = {Completeness in Hybrid Type Theory}, journal = {J. Philos. Log.}, volume = {43}, number = {2-3}, pages = {209--238}, year = {2014}, url = {https://doi.org/10.1007/s10992-012-9260-4}, doi = {10.1007/S10992-012-9260-4}, timestamp = {Sat, 05 Sep 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/jphil/ArecesBHM14.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/rsl/CarnielliCPR14, author = {Walter Alexandre Carnielli and Marcelo E. Coniglio and Rodrigo Podiacki and Tarc{\'{\i}}sio Rodrigues}, title = {On the Way to a wider Model Theory: Completeness theorems for First-order Logics of Formal Inconsistency}, journal = {Rev. Symb. Log.}, volume = {7}, number = {3}, pages = {548--578}, year = {2014}, url = {https://doi.org/10.1017/S1755020314000148}, doi = {10.1017/S1755020314000148}, timestamp = {Tue, 20 Aug 2019 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/rsl/CarnielliCPR14.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/tplp/NuttPS13, author = {Werner Nutt and Sergey Paramonov and Ognjen Savkovic}, title = {An {ASP} Approach to Query Completeness Reasoning}, journal = {Theory Pract. Log. Program.}, volume = {13}, number = {4-5-Online-Supplement}, year = {2013}, url = {http://static.cambridge.org/resource/id/urn:cambridge.org:id:binary:20161018085635834-0697:S1471068413000112:tlp2013005.pdf}, timestamp = {Thu, 13 Feb 2020 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/tplp/NuttPS13.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/iticse/CrescenziEK13, author = {Pierluigi Crescenzi and Emma Enstr{\"{o}}m and Viggo Kann}, editor = {Janet Carter and Ian Utting and Alison Clear}, title = {From theory to practice: NP-completeness for every {CS} student}, booktitle = {Innovation and Technology in Computer Science Education conference 2013, ITiCSE '13, Canterbury, United Kingdom - July 01 - 03, 2013}, pages = {16--21}, publisher = {{ACM}}, year = {2013}, url = {https://doi.org/10.1145/2462476.2465582}, doi = {10.1145/2462476.2465582}, timestamp = {Sun, 12 Feb 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/iticse/CrescenziEK13.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/mst/GuHP12, author = {Xiaoyang Gu and John M. Hitchcock and Aduri Pavan}, title = {Collapsing and Separating Completeness Notions Under Average-Case and Worst-Case Hypotheses}, journal = {Theory Comput. Syst.}, volume = {51}, number = {2}, pages = {248--265}, year = {2012}, url = {https://doi.org/10.1007/s00224-011-9365-0}, doi = {10.1007/S00224-011-9365-0}, timestamp = {Sun, 28 May 2017 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/mst/GuHP12.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@book{DBLP:books/cu/Goldreich2010, author = {Oded Goldreich}, title = {P, NP, and NP-Completeness: The Basics of Complexity Theory}, publisher = {Cambridge University Press}, year = {2010}, url = {http://www.wisdom.weizmann.ac.il/\&\#126;oded/bc-book.html}, doi = {10.1017/CBO9780511761355}, isbn = {978-0-521-12254-2}, timestamp = {Wed, 10 Jul 2019 01:00:00 +0200}, biburl = {https://dblp.org/rec/books/cu/Goldreich2010.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/fase/DarvasM10, author = {{\'{A}}d{\'{a}}m Darvas and Peter M{\"{u}}ller}, editor = {David S. Rosenblum and Gabriele Taentzer}, title = {Proving Consistency and Completeness of Model Classes Using Theory Interpretation}, booktitle = {Fundamental Approaches to Software Engineering, 13th International Conference, {FASE} 2010, Held as Part of the Joint European Conferences on Theory and Practice of Software, {ETAPS} 2010, Paphos, Cyprus, March 20-28, 2010. Proceedings}, series = {Lecture Notes in Computer Science}, volume = {6013}, pages = {218--232}, publisher = {Springer}, year = {2010}, url = {https://doi.org/10.1007/978-3-642-12029-9\_16}, doi = {10.1007/978-3-642-12029-9\_16}, timestamp = {Tue, 14 May 2019 10:00:54 +0200}, biburl = {https://dblp.org/rec/conf/fase/DarvasM10.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/mst/HitchcockPV08, author = {John M. Hitchcock and Aduri Pavan and N. V. Vinodchandran}, title = {Partial Bi-immunity, Scaled Dimension, and NP-Completeness}, journal = {Theory Comput. Syst.}, volume = {42}, number = {2}, pages = {131--142}, year = {2008}, url = {https://doi.org/10.1007/s00224-007-9000-2}, doi = {10.1007/S00224-007-9000-2}, timestamp = {Sun, 28 May 2017 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/mst/HitchcockPV08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@book{DBLP:books/daglib/0025071, author = {Peter B{\"{u}}rgisser}, title = {Completeness and Reduction in Algebraic Complexity Theory}, series = {Algorithms and computation in mathematics}, volume = {7}, publisher = {Springer}, year = {2000}, isbn = {978-3-540-66752-0}, timestamp = {Mon, 22 Jul 2019 01:00:00 +0200}, biburl = {https://dblp.org/rec/books/daglib/0025071.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/dmgt/HaluszczakV99, author = {Mariusz Haluszczak and Pavol Vateha}, title = {On the completeness of decomposable properties of graphs}, journal = {Discuss. Math. Graph Theory}, volume = {19}, number = {2}, pages = {229--236}, year = {1999}, url = {https://doi.org/10.7151/dmgt.1097}, doi = {10.7151/DMGT.1097}, timestamp = {Mon, 08 Jun 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/dmgt/HaluszczakV99.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/mscs/PrellerS96, author = {Anne Preller and Genevi{\`{e}}ve Simonet}, title = {Functional Completeness of the Free Locally Cartesian Closed Category an Interpretations of Martin-L{\"{o}}f's Theory of Dependent Types}, journal = {Math. Struct. Comput. Sci.}, volume = {6}, number = {4}, pages = {387--408}, year = {1996}, url = {https://doi.org/10.1017/S0960129500001080}, doi = {10.1017/S0960129500001080}, timestamp = {Wed, 01 Apr 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/mscs/PrellerS96.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/cc/Condon94, author = {Anne Condon}, title = {A Theory of Strict P-Completeness}, journal = {Comput. Complex.}, volume = {4}, pages = {220--241}, year = {1994}, url = {https://doi.org/10.1007/BF01206637}, doi = {10.1007/BF01206637}, timestamp = {Sun, 15 Mar 2020 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/cc/Condon94.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/ndjfl/CintioliT94, author = {Patrizio Cintioli and Sauro Tulipani}, title = {{\(\Sigma\)}\({}_{\mbox{1}}\)\({}^{\mbox{1}}\)-Completeness of a Fragment of the Theory of Trees With Subtree Relation}, journal = {Notre Dame J. Formal Log.}, volume = {35}, number = {3}, pages = {426--432}, year = {1994}, url = {https://doi.org/10.1305/ndjfl/1040511348}, doi = {10.1305/NDJFL/1040511348}, timestamp = {Thu, 21 May 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/ndjfl/CintioliT94.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/imperial/Pitts94, author = {Andrew M. Pitts}, editor = {Chris Hankin and Ian Mackie and Rajagopal Nagarajan}, title = {Completeness and Continuity Properties of Applicative Bisimulation}, booktitle = {Proceedings for the Second Imperial College Department of Computing Workshop on Theory and Formal Methods, M{\o}ller Centre, Cambridge, UK, 11-14 September 1994}, pages = {61}, publisher = {Imperial College Press}, year = {1994}, timestamp = {Wed, 20 Jun 2018 17:55:12 +0200}, biburl = {https://dblp.org/rec/conf/imperial/Pitts94.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/kgc/Petermann93, author = {Uwe Petermann}, editor = {Georg Gottlob and Alexander Leitsch and Daniele Mundici}, title = {Completeness of the Pool Calculus with an Open Built-in Theory}, booktitle = {Computational Logic and Proof Theory, Third Kurt G{\"{o}}del Colloquium, KGC'93, Brno, Czech Republic, August 24-27, 1993, Proceedings}, series = {Lecture Notes in Computer Science}, volume = {713}, pages = {277--288}, publisher = {Springer}, year = {1993}, url = {https://doi.org/10.1007/BFb0022576}, doi = {10.1007/BFB0022576}, timestamp = {Tue, 14 May 2019 10:00:52 +0200}, biburl = {https://dblp.org/rec/conf/kgc/Petermann93.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stacs/Condon92, author = {Anne Condon}, editor = {Alain Finkel and Matthias Jantzen}, title = {A Theory of Strict P-completeness}, booktitle = {{STACS} 92, 9th Annual Symposium on Theoretical Aspects of Computer Science, Cachan, France, February 13-15, 1992, Proceedings}, series = {Lecture Notes in Computer Science}, volume = {577}, pages = {33--44}, publisher = {Springer}, year = {1992}, url = {https://doi.org/10.1007/3-540-55210-3\_171}, doi = {10.1007/3-540-55210-3\_171}, timestamp = {Tue, 14 May 2019 10:00:48 +0200}, biburl = {https://dblp.org/rec/conf/stacs/Condon92.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/mst/Miyano89, author = {Satoru Miyano}, title = {The Lexicographically First Maximum Subgraph Problems: P-Completeness and {NC} Algorithms}, journal = {Math. Syst. Theory}, volume = {22}, number = {1}, pages = {47--73}, year = {1989}, url = {https://doi.org/10.1007/BF02088292}, doi = {10.1007/BF02088292}, timestamp = {Sun, 17 May 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/mst/Miyano89.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/jsyml/Powell76, author = {William C. Powell}, title = {A Completeness Theorem for Zermelo-Fraenkel Set Theory}, journal = {J. Symb. Log.}, volume = {41}, number = {2}, pages = {323--327}, year = {1976}, url = {https://doi.org/10.1017/S0022481200051379}, doi = {10.1017/S0022481200051379}, timestamp = {Sun, 28 May 2017 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/jsyml/Powell76.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.