Výsledek o hierarchii pro read-once rozhodovací diagramy s omezeným nedeterminismem paritního typu
Popis výsledku
Omezené rozhodovací diagramy jsou ve výpočtové složitosti zkoumány s cílem zkoumat prostorovou složitost sekvenčních výpočtů a v aplikacích jako datová struktura pro reprezentci Booleovských funkcí. V tomto článku jsou zkoumány (parity,k)-rozhodovací diagramy a (disjunktion,k)-rozhodovací diagramy, tj. rozhodovací diagramy začínající paritním nebo disjunktivním uzlem stupně k, jehož následníci jsou tvořeny k read-once rozhodovacími diagramy. Tento model je motivován studiem síly nedeterminismu v rozhodovacích diagramech jak z hlediska výpočtové složitosti tak z hlediska datových struktur. Jsou prezentovány metody pro dolní odhady a výsledek o hierarchii polynomiálně velkých (parity,k)-rozhodovacích diagramů a (disjunktion,k)-rozhodovacích diagramů vzhledem k parametru k.
Klíčová slova
read-once branching programsrestricted parity nondeterminismlower bounds on complexityhierarchy
Identifikátory výsledku
Kód výsledku v IS VaVaI
Výsledek na webu
—
DOI - Digital Object Identifier
—
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
A Hierarchy Result for Read-Once Branching Programs with Restricted Parity Nondeterminism
Popis výsledku v původním jazyce
Restricted branching programs are considered in complexity theory in order to study the space complexity of sequential computations and in applications as a data structure for Boolean functions. In this paper (parity,k)-branching programs and (disjunction,k)-branching programs are considered, i.e., branching programs starting with a parity- (disjunction-)node with a fan-out of k whose successors are k read-once branching programs. This model is motivated by the investigation of the power of nondeterminism in branching programs and of similar variants that have been considered as a data structure. Lower bound methods and hierarchy results for polynomial size (parity,k)- and (disjunction,k)-branching programs with respect to k are presented.
Název v anglickém jazyce
A Hierarchy Result for Read-Once Branching Programs with Restricted Parity Nondeterminism
Popis výsledku anglicky
Restricted branching programs are considered in complexity theory in order to study the space complexity of sequential computations and in applications as a data structure for Boolean functions. In this paper (parity,k)-branching programs and (disjunction,k)-branching programs are considered, i.e., branching programs starting with a parity- (disjunction-)node with a fan-out of k whose successors are k read-once branching programs. This model is motivated by the investigation of the power of nondeterminism in branching programs and of similar variants that have been considered as a data structure. Lower bound methods and hierarchy results for polynomial size (parity,k)- and (disjunction,k)-branching programs with respect to k are presented.
Klasifikace
Druh
Jx - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
BA - Obecná matematika
OECD FORD obor
—
Návaznosti výsledku
Projekt
LN00A056: Institut teoretické informatiky - Centrum mladé vědy
Návaznosti
Z - Vyzkumny zamer (s odkazem do CEZ)
Ostatní
Rok uplatnění
2005
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
Theoretical Computer Science
ISSN
0304-3975
e-ISSN
—
Svazek periodika
340
Číslo periodika v rámci svazku
-
Stát vydavatele periodika
NL - Nizozemsko
Počet stran výsledku
12
Strana od-do
594-605
Kód UT WoS článku
—
EID výsledku v databázi Scopus
—
Základní informace
Druh výsledku
Jx - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP
BA - Obecná matematika
Rok uplatnění
2005