A reducibility concept for problems defined in terms of ordered binary decision diagrams
Identifieur interne : 002A65 ( Main/Merge ); précédent : 002A64; suivant : 002A66A reducibility concept for problems defined in terms of ordered binary decision diagrams
Auteurs : Christoph Meinel [Allemagne] ; A. Slobodova [Allemagne]Source :
- Lecture notes in computer science [ 0302-9743 ] ; 1997.
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
Abstract
Reducibility concepts are fundamental in complexity theory. Usually, they are defined as follows: A problem II is reducible to a problem Σ if II can be computed using a program or device for Σ as a subroutine. However, this approach has its limitations if restricted computational models are considered. In the case of ordered binary decision diagrams (OBDDs), it allows merely to use the almost unmodified original program for the subroutine. Here we propose a new reducibility concept for OBDDs: We say that II is reducible to Σ if an OBDD for II can be constructed by applying a sequence of elementary operations to an OBDD for Σ. In contrast to previous reducibility notions, the suggested one is able to reflect the real needs of a reducibility concept in the context of OBDD-based complexity classes: it allows to reduce those problems to each other which are computable with the same amount of OBDD-resources and it gives a tool to carrying over lower and upper bounds.
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: 001383
- to stream PascalFrancis, to step Curation: 001609
- to stream PascalFrancis, to step Checkpoint: 001083
Links to Exploration step
Pascal:97-0359344Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">A reducibility concept for problems defined in terms of ordered binary decision diagrams</title><author><name sortKey="Meinel, C" sort="Meinel, C" uniqKey="Meinel C" first="C." last="Meinel">Christoph Meinel</name><affiliation wicri:level="1"><inist:fA14 i1="01"><s1>FB IV-Informatik, Universität Trier</s1><s2>54286 Trier</s2><s3>DEU</s3><sZ>1 aut.</sZ></inist:fA14><country>Allemagne</country><wicri:noRegion>54286 Trier</wicri:noRegion><wicri:noRegion>Universität Trier</wicri:noRegion><wicri:noRegion>54286 Trier</wicri:noRegion><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation><affiliation wicri:level="1"><inist:fA14 i1="02"><s1>ITWM-Trier, Bahnhofstr. 30-32</s1><s2>54292 Trier</s2><s3>DEU</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ></inist:fA14><country>Allemagne</country><wicri:noRegion>54292 Trier</wicri:noRegion><wicri:noRegion>Bahnhofstr. 30-32</wicri:noRegion><wicri:noRegion>54292 Trier</wicri:noRegion><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation></author><author><name sortKey="Slobodova, A" sort="Slobodova, A" uniqKey="Slobodova A" first="A." last="Slobodova">A. Slobodova</name><affiliation wicri:level="1"><inist:fA14 i1="02"><s1>ITWM-Trier, Bahnhofstr. 30-32</s1><s2>54292 Trier</s2><s3>DEU</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ></inist:fA14><country>Allemagne</country><wicri:noRegion>54292 Trier</wicri:noRegion><wicri:noRegion>Bahnhofstr. 30-32</wicri:noRegion><wicri:noRegion>54292 Trier</wicri:noRegion></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">INIST</idno><idno type="inist">97-0359344</idno><date when="1997">1997</date><idno type="stanalyst">PASCAL 97-0359344 INIST</idno><idno type="RBID">Pascal:97-0359344</idno><idno type="wicri:Area/PascalFrancis/Corpus">001383</idno><idno type="wicri:Area/PascalFrancis/Curation">001609</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">001083</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">001083</idno><idno type="wicri:doubleKey">0302-9743:1997:Meinel C:a:reducibility:concept</idno><idno type="wicri:Area/Main/Merge">002A65</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">A reducibility concept for problems defined in terms of ordered binary decision diagrams</title><author><name sortKey="Meinel, C" sort="Meinel, C" uniqKey="Meinel C" first="C." last="Meinel">Christoph Meinel</name><affiliation wicri:level="1"><inist:fA14 i1="01"><s1>FB IV-Informatik, Universität Trier</s1><s2>54286 Trier</s2><s3>DEU</s3><sZ>1 aut.</sZ></inist:fA14><country>Allemagne</country><wicri:noRegion>54286 Trier</wicri:noRegion><wicri:noRegion>Universität Trier</wicri:noRegion><wicri:noRegion>54286 Trier</wicri:noRegion><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation><affiliation wicri:level="1"><inist:fA14 i1="02"><s1>ITWM-Trier, Bahnhofstr. 30-32</s1><s2>54292 Trier</s2><s3>DEU</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ></inist:fA14><country>Allemagne</country><wicri:noRegion>54292 Trier</wicri:noRegion><wicri:noRegion>Bahnhofstr. 30-32</wicri:noRegion><wicri:noRegion>54292 Trier</wicri:noRegion><placeName><settlement type="city">Trèves (Allemagne)</settlement><region type="land" nuts="1">Rhénanie-Palatinat</region></placeName><orgName type="university">Université de Trèves</orgName></affiliation></author><author><name sortKey="Slobodova, A" sort="Slobodova, A" uniqKey="Slobodova A" first="A." last="Slobodova">A. Slobodova</name><affiliation wicri:level="1"><inist:fA14 i1="02"><s1>ITWM-Trier, Bahnhofstr. 30-32</s1><s2>54292 Trier</s2><s3>DEU</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ></inist:fA14><country>Allemagne</country><wicri:noRegion>54292 Trier</wicri:noRegion><wicri:noRegion>Bahnhofstr. 30-32</wicri:noRegion><wicri:noRegion>54292 Trier</wicri:noRegion></affiliation></author></analytic><series><title level="j" type="main">Lecture notes in computer science</title><idno type="ISSN">0302-9743</idno><imprint><date when="1997">1997</date></imprint></series></biblStruct></sourceDesc><seriesStmt><title level="j" type="main">Lecture notes in computer science</title><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Complexity</term><term>Computational complexity</term><term>Decision support system</term><term>Lower bound</term><term>Polynomial time</term><term>Reducibility</term><term>Turing machine</term><term>Upper bound</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Réductibilité</term><term>Complexité</term><term>Complexité calcul</term><term>Système aide décision</term><term>Borne supérieure</term><term>Borne inférieure</term><term>Machine Turing</term><term>Temps polynomial</term><term>Diagramme décision binaire</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Reducibility concepts are fundamental in complexity theory. Usually, they are defined as follows: A problem II is reducible to a problem Σ if II can be computed using a program or device for Σ as a subroutine. However, this approach has its limitations if restricted computational models are considered. In the case of ordered binary decision diagrams (OBDDs), it allows merely to use the almost unmodified original program for the subroutine. Here we propose a new reducibility concept for OBDDs: We say that II is reducible to Σ if an OBDD for II can be constructed by applying a sequence of elementary operations to an OBDD for Σ. In contrast to previous reducibility notions, the suggested one is able to reflect the real needs of a reducibility concept in the context of OBDD-based complexity classes: it allows to reduce those problems to each other which are computable with the same amount of OBDD-resources and it gives a tool to carrying over lower and upper bounds.</div></front></TEI><affiliations><list><country><li>Allemagne</li></country><region><li>Rhénanie-Palatinat</li></region><settlement><li>Trèves (Allemagne)</li></settlement><orgName><li>Université de Trèves</li></orgName></list><tree><country name="Allemagne"><region name="Rhénanie-Palatinat"><name sortKey="Meinel, C" sort="Meinel, C" uniqKey="Meinel C" first="C." last="Meinel">Christoph Meinel</name></region><name sortKey="Meinel, C" sort="Meinel, C" uniqKey="Meinel C" first="C." last="Meinel">Christoph Meinel</name><name sortKey="Slobodova, A" sort="Slobodova, A" uniqKey="Slobodova A" first="A." last="Slobodova">A. Slobodova</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Main/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002A65 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 002A65 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Main
|étape= Merge
|type= RBID
|clé= Pascal:97-0359344
|texte= A reducibility concept for problems defined in terms of ordered binary decision diagrams
}}
| This area was generated with Dilib version V0.6.31. |  |