The complexity of some complementation problems
Identifieur interne : 002289 ( Istex/Corpus ); précédent : 002288; suivant : 002290The complexity of some complementation problems
Auteurs : David A. Plaisted ; Gregory KucherovSource :
- 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 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><mods:affiliation>E-mail: plaisted@cs.unc.edu</mods:affiliation></affiliation><affiliation><mods:affiliation>Department of Computer Science, University of North Carolina at Chapel Hill, Chapel Hill, NC27599-3175, USA</mods:affiliation></affiliation></author><author><name sortKey="Kucherov, Gregory" sort="Kucherov, Gregory" uniqKey="Kucherov G" first="Gregory" last="Kucherov">Gregory Kucherov</name><affiliation><mods:affiliation>E-mail: plaisted@cs.unc.edu</mods:affiliation></affiliation><affiliation><mods:affiliation>LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P. 101, 54602 Villers-lès-Nancy, France</mods:affiliation></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></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><mods:affiliation>E-mail: plaisted@cs.unc.edu</mods:affiliation></affiliation><affiliation><mods:affiliation>Department of Computer Science, University of North Carolina at Chapel Hill, Chapel Hill, NC27599-3175, USA</mods:affiliation></affiliation></author><author><name sortKey="Kucherov, Gregory" sort="Kucherov, Gregory" uniqKey="Kucherov G" first="Gregory" last="Kucherov">Gregory Kucherov</name><affiliation><mods:affiliation>E-mail: plaisted@cs.unc.edu</mods:affiliation></affiliation><affiliation><mods:affiliation>LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P. 101, 54602 Villers-lès-Nancy, France</mods:affiliation></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><istex><corpusName>elsevier</corpusName><keywords><teeft><json:string>linear terms</json:string><json:string>hierarchical</json:string><json:string>complement representation</json:string><json:string>disjoint</json:string><json:string>kucherov</json:string><json:string>ground terms</json:string><json:string>nite</json:string><json:string>plaisted</json:string><json:string>lassez</json:string><json:string>springer</json:string><json:string>kucherov information processing letters</json:string><json:string>lecture notes</json:string><json:string>ground reducibility</json:string><json:string>exponential</json:string><json:string>constant symbols</json:string><json:string>complement problem</json:string><json:string>hierarchical sets</json:string><json:string>logic programming</json:string><json:string>chapel hill</json:string><json:string>maximal depth</json:string><json:string>complement problems</json:string><json:string>distinct terms</json:string><json:string>computer science</json:string><json:string>function symbols</json:string><json:string>worst case</json:string><json:string>complexity questions</json:string><json:string>nite complement representation</json:string><json:string>other hand</json:string><json:string>empty complement</json:string><json:string>elsevier science</json:string><json:string>ground term</json:string><json:string>international workshop</json:string><json:string>symbol size</json:string><json:string>model building</json:string><json:string>smallest position</json:string><json:string>atomic representations</json:string><json:string>elementary substitution</json:string><json:string>other term</json:string><json:string>ieee symposium</json:string><json:string>constant size</json:string><json:string>such terms</json:string><json:string>exponential size</json:string><json:string>herbrand models</json:string><json:string>position form</json:string><json:string>complementation problem</json:string><json:string>complement representation problem</json:string><json:string>computational complexity</json:string><json:string>normal forms</json:string><json:string>quadratic</json:string></teeft></keywords><author><json:item><name>David A. Plaisted</name><affiliations><json:string>E-mail: plaisted@cs.unc.edu</json:string><json:string>Department of Computer Science, University of North Carolina at Chapel Hill, Chapel Hill, NC27599-3175, USA</json:string></affiliations></json:item><json:item><name>Gregory Kucherov</name><affiliations><json:string>E-mail: plaisted@cs.unc.edu</json:string><json:string>LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P. 101, 54602 Villers-lès-Nancy, France</json:string></affiliations></json:item></author><subject><json:item><lang><json:string>eng</json:string></lang><value>Term</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Ground term</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Ground instance</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Complement representation</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Computational complexity</value></json:item></subject><arkIstex>ark:/67375/6H6-W72M07NQ-S</arkIstex><language><json:string>eng</json:string></language><originalGenre><json:string>Short communication</json:string></originalGenre><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.</abstract><qualityIndicators><score>7.368</score><pdfWordCount>4612</pdfWordCount><pdfCharCount>21892</pdfCharCount><pdfVersion>1.2</pdfVersion><pdfPageCount>7</pdfPageCount><pdfPageSize>543 x 744 pts</pdfPageSize><refBibsNative>false</refBibsNative><abstractWordCount>63</abstractWordCount><abstractCharCount>376</abstractCharCount><keywordCount>5</keywordCount></qualityIndicators><title>The complexity of some complementation problems</title><pii><json:string>S0020-0190(99)00102-7</json:string></pii><genre><json:string>brief-communication</json:string></genre><host><title>Information Processing Letters</title><language><json:string>unknown</json:string></language><publicationDate>1999</publicationDate><issn><json:string>0020-0190</json:string></issn><pii><json:string>S0020-0190(00)X0110-X</json:string></pii><volume>71</volume><issue>3–4</issue><pages><first>159</first><last>165</last></pages><genre><json:string>journal</json:string></genre></host><namedEntities><unitex><date><json:string>1999</json:string></date><geogName></geogName><orgName><json:string>France Received</json:string></orgName><orgName_funder></orgName_funder><orgName_provider></orgName_provider><persName><json:string>Miki Hermann</json:string><json:string>Laurent Juban</json:string><json:string>G. Kucherov</json:string><json:string>A. Plaisted</json:string><json:string>Hélène Kirchner</json:string><json:string>D.A. Plaisted</json:string></persName><placeName></placeName><ref_url></ref_url><ref_bibl><json:string>Lassez et al. [20]</json:string><json:string>[13,12]</json:string><json:string>[12,9,1,4,8]</json:string><json:string>[21, 16,11,14,15,3]</json:string><json:string>[11]</json:string><json:string>[17]</json:string><json:string>[10,19]</json:string><json:string>[5]</json:string><json:string>[4,20]</json:string><json:string>[7]</json:string></ref_bibl><bibl></bibl></unitex></namedEntities><ark><json:string>ark:/67375/6H6-W72M07NQ-S</json:string></ark><categories><wos><json:string>1 - science</json:string><json:string>2 - computer science, information systems</json:string></wos><scienceMetrix><json:string>1 - applied sciences</json:string><json:string>2 - information & communication technologies</json:string><json:string>3 - computation theory & mathematics</json:string></scienceMetrix><scopus><json:string>1 - Physical Sciences</json:string><json:string>2 - Computer Science</json:string><json:string>3 - Computer Science Applications</json:string><json:string>1 - Physical Sciences</json:string><json:string>2 - Computer Science</json:string><json:string>3 - Information Systems</json:string><json:string>1 - Physical Sciences</json:string><json:string>2 - Computer Science</json:string><json:string>3 - Signal Processing</json:string><json:string>1 - Physical Sciences</json:string><json:string>2 - Mathematics</json:string><json:string>3 - Theoretical Computer Science</json:string></scopus><inist><json:string>1 - sciences appliquees, technologies et medecines</json:string><json:string>2 - sciences exactes et technologie</json:string><json:string>3 - sciences et techniques communes</json:string><json:string>4 - mathematiques</json:string></inist></categories><publicationDate>1999</publicationDate><copyrightDate>1999</copyrightDate><doi><json:string>10.1016/S0020-0190(99)00102-7</json:string></doi><id>953B751135141EFA971202B8DADFF3D9105C6C90</id><score>1</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/ark:/67375/6H6-W72M07NQ-S/fulltext.pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/ark:/67375/6H6-W72M07NQ-S/bundle.zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/ark:/67375/6H6-W72M07NQ-S/fulltext.tei"><teiHeader><fileDesc><titleStmt><title level="a">The complexity of some complementation problems</title></titleStmt><publicationStmt><authority>ISTEX</authority><publisher scheme="https://scientific-publisher.data.istex.fr">ELSEVIER</publisher><availability><licence><p>©1999 Elsevier Science B.V.</p></licence><p scheme="https://loaded-corpus.data.istex.fr/ark:/67375/XBH-HKKZVM7B-M">elsevier</p></availability><date>1999</date></publicationStmt><notesStmt><note type="brief-communication" scheme="https://content-type.data.istex.fr/ark:/67375/XTP-S9SX2MFS-0">brief-communication</note><note type="journal" scheme="https://publication-type.data.istex.fr/ark:/67375/JMC-0GLKJH51-B">journal</note><note>communicated by H. Ganzinger</note></notesStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a">The complexity of some complementation problems</title><author xml:id="author-0000"><persName><forename type="first">David A.</forename><surname>Plaisted</surname></persName><email>plaisted@cs.unc.edu</email><note type="correspondence"><p>Corresponding author.</p></note><affiliation>Department of Computer Science, University of North Carolina at Chapel Hill, Chapel Hill, NC27599-3175, USA</affiliation></author><author xml:id="author-0001"><persName><forename type="first">Gregory</forename><surname>Kucherov</surname></persName><email>plaisted@cs.unc.edu</email><affiliation>LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P. 101, 54602 Villers-lès-Nancy, France</affiliation></author><idno type="istex">953B751135141EFA971202B8DADFF3D9105C6C90</idno><idno type="ark">ark:/67375/6H6-W72M07NQ-S</idno><idno type="DOI">10.1016/S0020-0190(99)00102-7</idno><idno type="PII">S0020-0190(99)00102-7</idno></analytic><monogr><title level="j">Information Processing Letters</title><title level="j" type="abbrev">IPL</title><idno type="pISSN">0020-0190</idno><idno type="PII">S0020-0190(00)X0110-X</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="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></monogr></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>1999</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>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.</p></abstract><textClass><keywords scheme="keyword"><list><head>Keywords</head><item><term>Term</term></item><item><term>Ground term</term></item><item><term>Ground instance</term></item><item><term>Complement representation</term></item><item><term>Computational complexity</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="1999">Published</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/ark:/67375/6H6-W72M07NQ-S/fulltext.txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Elsevier converted-article found"><istex:xmlDeclaration>version="1.0" encoding="utf-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//ES//DTD journal article DTD version 4.5.2//EN//XML" URI="art452.dtd" name="istex:docType"></istex:docType><istex:document><converted-article version="4.5.2" docsubtype="sco"><item-info><jid>IPL</jid><aid>2228</aid><ce:pii>S0020-0190(99)00102-7</ce:pii><ce:doi>10.1016/S0020-0190(99)00102-7</ce:doi><ce:copyright type="full-transfer" year="1999">Elsevier Science B.V.</ce:copyright></item-info><head><ce:title>The complexity of some complementation problems</ce:title><ce:author-group><ce:author><ce:given-name>David A.</ce:given-name><ce:surname>Plaisted</ce:surname><ce:cross-ref refid="ID002"><ce:sup>a</ce:sup></ce:cross-ref><ce:cross-ref refid="CORR1">*</ce:cross-ref><ce:e-address>plaisted@cs.unc.edu</ce:e-address></ce:author><ce:author><ce:given-name>Gregory</ce:given-name><ce:surname>Kucherov</ce:surname><ce:cross-ref refid="ID004"><ce:sup>b</ce:sup></ce:cross-ref><ce:e-address>kucherov@loria.fr</ce:e-address></ce:author><ce:affiliation id="ID002"><ce:label>a</ce:label><ce:textfn>Department of Computer Science, University of North Carolina at Chapel Hill, Chapel Hill, NC27599-3175, USA</ce:textfn></ce:affiliation><ce:affiliation id="ID004"><ce:label>b</ce:label><ce:textfn>LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P. 101, 54602 Villers-lès-Nancy, France</ce:textfn></ce:affiliation><ce:correspondence id="CORR1"><ce:label>*</ce:label><ce:text>Corresponding author.</ce:text></ce:correspondence></ce:author-group><ce:date-received day="18" month="8" year="1998"></ce:date-received><ce:miscellaneous>communicated by H. Ganzinger</ce:miscellaneous><ce:abstract><ce:section-title>Abstract</ce:section-title><ce:abstract-sec><ce:simple-para>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.</ce:simple-para></ce:abstract-sec></ce:abstract><ce:keywords><ce:section-title>Keywords</ce:section-title><ce:keyword><ce:text>Term</ce:text></ce:keyword><ce:keyword><ce:text>Ground term</ce:text></ce:keyword><ce:keyword><ce:text>Ground instance</ce:text></ce:keyword><ce:keyword><ce:text>Complement representation</ce:text></ce:keyword><ce:keyword><ce:text>Computational complexity</ce:text></ce:keyword></ce:keywords></head></converted-article></istex:document></istex:metadataXml><mods version="3.6"><titleInfo><title>The complexity of some complementation problems</title></titleInfo><titleInfo type="alternative" contentType="CDATA"><title>The complexity of some complementation problems</title></titleInfo><name type="personal"><namePart type="given">David A.</namePart><namePart type="family">Plaisted</namePart><affiliation>E-mail: plaisted@cs.unc.edu</affiliation><affiliation>Department of Computer Science, University of North Carolina at Chapel Hill, Chapel Hill, NC27599-3175, USA</affiliation><description>Corresponding author.</description><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Gregory</namePart><namePart type="family">Kucherov</namePart><affiliation>E-mail: plaisted@cs.unc.edu</affiliation><affiliation>LORIA/INRIA-Lorraine, 615, rue du Jardin Botanique, B.P. 101, 54602 Villers-lès-Nancy, France</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="brief-communication" displayLabel="Short communication" authority="ISTEX" authorityURI="https://content-type.data.istex.fr" valueURI="https://content-type.data.istex.fr/ark:/67375/XTP-S9SX2MFS-0">brief-communication</genre><originInfo><publisher>ELSEVIER</publisher><dateIssued encoding="w3cdtf">1999</dateIssued><copyrightDate encoding="w3cdtf">1999</copyrightDate></originInfo><language><languageTerm type="code" authority="iso639-2b">eng</languageTerm><languageTerm type="code" authority="rfc3066">en</languageTerm></language><abstract 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.</abstract><note>communicated by H. Ganzinger</note><subject><genre>Keywords</genre><topic>Term</topic><topic>Ground term</topic><topic>Ground instance</topic><topic>Complement representation</topic><topic>Computational complexity</topic></subject><relatedItem type="host"><titleInfo><title>Information Processing Letters</title></titleInfo><titleInfo type="abbreviated"><title>IPL</title></titleInfo><genre type="journal" authority="ISTEX" authorityURI="https://publication-type.data.istex.fr" valueURI="https://publication-type.data.istex.fr/ark:/67375/JMC-0GLKJH51-B">journal</genre><originInfo><publisher>ELSEVIER</publisher><dateIssued encoding="w3cdtf">1999</dateIssued></originInfo><identifier type="ISSN">0020-0190</identifier><identifier type="PII">S0020-0190(00)X0110-X</identifier><part><date>1999</date><detail type="volume"><number>71</number><caption>vol.</caption></detail><detail type="issue"><number>3–4</number><caption>no.</caption></detail><extent unit="issue-pages"><start>97</start><end>172</end></extent><extent unit="pages"><start>159</start><end>165</end></extent></part></relatedItem><identifier type="istex">953B751135141EFA971202B8DADFF3D9105C6C90</identifier><identifier type="ark">ark:/67375/6H6-W72M07NQ-S</identifier><identifier type="DOI">10.1016/S0020-0190(99)00102-7</identifier><identifier type="PII">S0020-0190(99)00102-7</identifier><accessCondition type="use and reproduction" contentType="copyright">©1999 Elsevier Science B.V.</accessCondition><recordInfo><recordContentSource authority="ISTEX" authorityURI="https://loaded-corpus.data.istex.fr" valueURI="https://loaded-corpus.data.istex.fr/ark:/67375/XBH-HKKZVM7B-M">elsevier</recordContentSource><recordOrigin>Elsevier Science B.V., ©1999</recordOrigin></recordInfo></mods><json:item><extension>json</extension><original>false</original><mimetype>application/json</mimetype><uri>https://api.istex.fr/ark:/67375/6H6-W72M07NQ-S/record.json</uri></json:item></metadata><serie></serie></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002289 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 002289 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:953B751135141EFA971202B8DADFF3D9105C6C90
|texte= The complexity of some complementation problems
}}
| This area was generated with Dilib version V0.6.33. |  |