Search dblp for Publications

export results for "p-completeness theory"

 download as .bib file

@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}
}
a service of  Schloss Dagstuhl - Leibniz Center for Informatics