Inductive Counting for Width-Restricted Branching Programs
Identifieur interne : 002C52 ( Main/Merge ); précédent : 002C51; suivant : 002C53Inductive Counting for Width-Restricted Branching Programs
Auteurs : Carsten Damm [Allemagne] ; Markus Holzer [Allemagne]Source :
- Information and Computation [ 0890-5401 ] ; 1996.
Abstract
As an application of the inductive counting technique to a circuit-like model, we prove that complementation on nondeterministic branching programs can be done without increasing the width excessively. A consequence of this result is that the class of languages recognized by a generalization of nonuniform finite automata to nonconstant space is closed under complement.
Url:
DOI: 10.1006/inco.1996.0084
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 000C05
- to stream Istex, to step Curation: 000B34
- to stream Istex, to step Checkpoint: 001052
Links to Exploration step
ISTEX:8B1C3805ABE92048EA0E36B76B47C0AE7A75FDA9Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Inductive Counting for Width-Restricted Branching Programs</title><author><name sortKey="Damm, Carsten" sort="Damm, Carsten" uniqKey="Damm C" first="Carsten" last="Damm">Carsten Damm</name></author><author><name sortKey="Holzer, Markus" sort="Holzer, Markus" uniqKey="Holzer M" first="Markus" last="Holzer">Markus Holzer</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:8B1C3805ABE92048EA0E36B76B47C0AE7A75FDA9</idno><date when="1996" year="1996">1996</date><idno type="doi">10.1006/inco.1996.0084</idno><idno type="url">https://api.istex.fr/document/8B1C3805ABE92048EA0E36B76B47C0AE7A75FDA9/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">000C05</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000C05</idno><idno type="wicri:Area/Istex/Curation">000B34</idno><idno type="wicri:Area/Istex/Checkpoint">001052</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">001052</idno><idno type="wicri:doubleKey">0890-5401:1996:Damm C:inductive:counting:for</idno><idno type="wicri:Area/Main/Merge">002C52</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Inductive Counting for Width-Restricted Branching Programs</title><author><name sortKey="Damm, Carsten" sort="Damm, Carsten" uniqKey="Damm C" first="Carsten" last="Damm">Carsten Damm</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>FB IV—Informatik, Universität Trier, D-54286, Trier</wicri:regionArea><wicri:noRegion>54286, Trier</wicri:noRegion><wicri:noRegion>Trier</wicri:noRegion></affiliation></author><author><name sortKey="Holzer, Markus" sort="Holzer, Markus" uniqKey="Holzer M" first="Markus" last="Holzer">Markus Holzer</name><affiliation wicri:level="3"><country xml:lang="fr">Allemagne</country><wicri:regionArea>Wilhelm-Schickard Institut für Informatik, Universität Tübingen, Sand 13, D-72076, Tübingen</wicri:regionArea><placeName><region type="land" nuts="1">Bade-Wurtemberg</region><region type="district" nuts="2">District de Tübingen</region><settlement type="city">Tübingen</settlement></placeName></affiliation></author></analytic><monogr></monogr><series><title level="j">Information and Computation</title><title level="j" type="abbrev">YINCO</title><idno type="ISSN">0890-5401</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1996">1996</date><biblScope unit="volume">130</biblScope><biblScope unit="issue">1</biblScope><biblScope unit="page" from="91">91</biblScope><biblScope unit="page" to="99">99</biblScope></imprint><idno type="ISSN">0890-5401</idno></series><idno type="istex">8B1C3805ABE92048EA0E36B76B47C0AE7A75FDA9</idno><idno type="DOI">10.1006/inco.1996.0084</idno><idno type="PII">S0890-5401(96)90084-X</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0890-5401</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">As an application of the inductive counting technique to a circuit-like model, we prove that complementation on nondeterministic branching programs can be done without increasing the width excessively. A consequence of this result is that the class of languages recognized by a generalization of nonuniform finite automata to nonconstant space is closed under complement.</div></front></TEI></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 002C52 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 002C52 | 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é= ISTEX:8B1C3805ABE92048EA0E36B76B47C0AE7A75FDA9
|texte= Inductive Counting for Width-Restricted Branching Programs
}}
| This area was generated with Dilib version V0.6.31. |  |