The complexity of some complementation problems
Identifieur interne : 002258 ( Istex/Curation ); précédent : 002257; suivant : 002259The complexity of some complementation problems
Auteurs : David A. Plaisted [États-Unis] ; Gregory Kucherov [États-Unis, France]Source :
- Information Processing Letters [ 0020-0190 ] ; 1999.
English descriptors
- Teeft :
- Atomic representations, Chapel hill, Complement problem, Complement problems, Complement representation, Complement representation problem, Complementation problem, Complexity questions, Computational complexity, Computer science, Constant size, Constant symbols, Disjoint, Distinct terms, Elementary substitution, Elsevier science, Empty complement, Exponential, Exponential size, Function symbols, Ground reducibility, Ground term, Ground terms, Herbrand models, Hierarchical, Hierarchical sets, Ieee symposium, International workshop, Kucherov, Kucherov information processing letters, Lassez, Lecture notes, Linear terms, Logic programming, Maximal depth, Model building, Nite, Nite complement representation, Normal forms, Other hand, Other term, Plaisted, Position form, Quadratic, Smallest position, Springer, Such terms, Symbol size, Worst case.
Abstract
Abstract: We study the computational complexity of the problem of computing a complement representation for a set of terms. Depending on the class of sets considered, some sets are shown to have an exponential complement representation in the worst case, and some are shown to have a polynomial one. The complexity of deciding if a set has an empty complement is also studied.
Url:
DOI: 10.1016/S0020-0190(99)00102-7
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: Pour aller vers cette notice dans l'étape Curation :002289
Links to Exploration step
ISTEX:953B751135141EFA971202B8DADFF3D9105C6C90Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>The complexity of some complementation problems</title><author><name sortKey="Plaisted, David A" sort="Plaisted, David A" uniqKey="Plaisted D" first="David A." last="Plaisted">David A. Plaisted</name><affiliation wicri:level="1"><mods:affiliation>E-mail: plaisted@cs.unc.edu</mods:affiliation><country wicri:rule="url">États-Unis</country></affiliation><affiliation wicri:level="1"><mods:affiliation>Department of Computer Science, University of North Carolina at Chapel Hill, Chapel Hill, NC27599-3175, USA</mods:affiliation><country xml:lang="fr">États-Unis</country><wicri:regionArea>Department of Computer Science, University of North Carolina at Chapel Hill, Chapel Hill, NC27599-3175</wicri:regionArea></affiliation></author><author><name sortKey="Kucherov, Gregory" sort="Kucherov, Gregory" uniqKey="Kucherov G" first="Gregory" last="Kucherov">Gregory Kucherov</name><affiliation wicri:level="1"><mods:affiliation>E-mail: plaisted@cs.unc.edu</mods:affiliation><country wicri:rule="url">États-Unis</country></affiliation><affiliation wicri:level="1"><mods:affiliation>LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P. 101, 54602 Villers-lès-Nancy, France</mods:affiliation><country xml:lang="fr">France</country><wicri:regionArea>LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P. 101, 54602 Villers-lès-Nancy</wicri:regionArea></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:953B751135141EFA971202B8DADFF3D9105C6C90</idno><date when="1999" year="1999">1999</date><idno type="doi">10.1016/S0020-0190(99)00102-7</idno><idno type="url">https://api.istex.fr/ark:/67375/6H6-W72M07NQ-S/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">002289</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">002289</idno><idno type="wicri:Area/Istex/Curation">002258</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a">The complexity of some complementation problems</title><author><name sortKey="Plaisted, David A" sort="Plaisted, David A" uniqKey="Plaisted D" first="David A." last="Plaisted">David A. Plaisted</name><affiliation wicri:level="1"><mods:affiliation>E-mail: plaisted@cs.unc.edu</mods:affiliation><country wicri:rule="url">États-Unis</country></affiliation><affiliation wicri:level="1"><mods:affiliation>Department of Computer Science, University of North Carolina at Chapel Hill, Chapel Hill, NC27599-3175, USA</mods:affiliation><country xml:lang="fr">États-Unis</country><wicri:regionArea>Department of Computer Science, University of North Carolina at Chapel Hill, Chapel Hill, NC27599-3175</wicri:regionArea></affiliation></author><author><name sortKey="Kucherov, Gregory" sort="Kucherov, Gregory" uniqKey="Kucherov G" first="Gregory" last="Kucherov">Gregory Kucherov</name><affiliation wicri:level="1"><mods:affiliation>E-mail: plaisted@cs.unc.edu</mods:affiliation><country wicri:rule="url">États-Unis</country></affiliation><affiliation wicri:level="1"><mods:affiliation>LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P. 101, 54602 Villers-lès-Nancy, France</mods:affiliation><country xml:lang="fr">France</country><wicri:regionArea>LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P. 101, 54602 Villers-lès-Nancy</wicri:regionArea></affiliation></author></analytic><monogr></monogr><series><title level="j">Information Processing Letters</title><title level="j" type="abbrev">IPL</title><idno type="ISSN">0020-0190</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1999">1999</date><biblScope unit="volume">71</biblScope><biblScope unit="issue">3–4</biblScope><biblScope unit="page" from="159">159</biblScope><biblScope unit="page" to="165">165</biblScope></imprint><idno type="ISSN">0020-0190</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0020-0190</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="Teeft" xml:lang="en"><term>Atomic representations</term><term>Chapel hill</term><term>Complement problem</term><term>Complement problems</term><term>Complement representation</term><term>Complement representation problem</term><term>Complementation problem</term><term>Complexity questions</term><term>Computational complexity</term><term>Computer science</term><term>Constant size</term><term>Constant symbols</term><term>Disjoint</term><term>Distinct terms</term><term>Elementary substitution</term><term>Elsevier science</term><term>Empty complement</term><term>Exponential</term><term>Exponential size</term><term>Function symbols</term><term>Ground reducibility</term><term>Ground term</term><term>Ground terms</term><term>Herbrand models</term><term>Hierarchical</term><term>Hierarchical sets</term><term>Ieee symposium</term><term>International workshop</term><term>Kucherov</term><term>Kucherov information processing letters</term><term>Lassez</term><term>Lecture notes</term><term>Linear terms</term><term>Logic programming</term><term>Maximal depth</term><term>Model building</term><term>Nite</term><term>Nite complement representation</term><term>Normal forms</term><term>Other hand</term><term>Other term</term><term>Plaisted</term><term>Position form</term><term>Quadratic</term><term>Smallest position</term><term>Springer</term><term>Such terms</term><term>Symbol size</term><term>Worst case</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: We study the computational complexity of the problem of computing a complement representation for a set of terms. Depending on the class of sets considered, some sets are shown to have an exponential complement representation in the worst case, and some are shown to have a polynomial one. The complexity of deciding if a set has an empty complement is also studied.</div></front></TEI></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Istex/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002258 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Curation/biblio.hfd -nk 002258 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Istex
|étape= Curation
|type= RBID
|clé= ISTEX:953B751135141EFA971202B8DADFF3D9105C6C90
|texte= The complexity of some complementation problems
}}
| This area was generated with Dilib version V0.6.33. |  |