This HTML5 document contains 41 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
n19http://linked.opendata.cz/ontology/domain/vavai/riv/typAkce/
dctermshttp://purl.org/dc/terms/
n10http://localhost/temp/predkladatel/
n7http://purl.org/net/nknouf/ns/bibtex#
n20http://linked.opendata.cz/resource/domain/vavai/projekt/
n12http://linked.opendata.cz/resource/domain/vavai/riv/tvurce/
n9http://linked.opendata.cz/ontology/domain/vavai/
n4https://schema.org/
shttp://schema.org/
skoshttp://www.w3.org/2004/02/skos/core#
n3http://linked.opendata.cz/ontology/domain/vavai/riv/
n18http://linked.opendata.cz/resource/domain/vavai/vysledek/RIV%2F00216224%3A14330%2F09%3A00039313%21RIV10-MSM-14330___/
n2http://linked.opendata.cz/resource/domain/vavai/vysledek/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n17http://linked.opendata.cz/ontology/domain/vavai/riv/klicoveSlovo/
n21http://linked.opendata.cz/ontology/domain/vavai/riv/duvernostUdaju/
xsdhhttp://www.w3.org/2001/XMLSchema#
n8http://linked.opendata.cz/ontology/domain/vavai/riv/jazykVysledku/
n6http://linked.opendata.cz/ontology/domain/vavai/riv/aktivita/
n15http://linked.opendata.cz/ontology/domain/vavai/riv/druhVysledku/
n13http://linked.opendata.cz/ontology/domain/vavai/riv/obor/
n5http://reference.data.gov.uk/id/gregorian-year/

Statements

Subject Item
n2:RIV%2F00216224%3A14330%2F09%3A00039313%21RIV10-MSM-14330___
rdf:type
n9:Vysledek skos:Concept
dcterms:description
We investigate the problem of evaluating memory consumption for systems modelled by probabilistic pushdown automata (pPDA). The space needed by a run of a pPDA is the maximal height reached by the stack during the run. The problem is motivated by the investigation of depth-first computations that play an important role for space-efficient schedulings of multithreaded programs. We study the computation of both the distribution of the memory consumption and its expectation. For the distribution, we develop an efficient approximation method. For the expected memory consumption, we show that whether it is infinite can be decided in polynomial time for stateless pPDA (pBPA) and in polynomial space for pPDA. We also provide an iterative method for approximating the expectation. We investigate the problem of evaluating memory consumption for systems modelled by probabilistic pushdown automata (pPDA). The space needed by a run of a pPDA is the maximal height reached by the stack during the run. The problem is motivated by the investigation of depth-first computations that play an important role for space-efficient schedulings of multithreaded programs. We study the computation of both the distribution of the memory consumption and its expectation. For the distribution, we develop an efficient approximation method. For the expected memory consumption, we show that whether it is infinite can be decided in polynomial time for stateless pPDA (pBPA) and in polynomial space for pPDA. We also provide an iterative method for approximating the expectation.
dcterms:title
On the memory consumption of probabilistic pushdown automata On the memory consumption of probabilistic pushdown automata
skos:prefLabel
On the memory consumption of probabilistic pushdown automata On the memory consumption of probabilistic pushdown automata
skos:notation
RIV/00216224:14330/09:00039313!RIV10-MSM-14330___
n3:aktivita
n6:P
n3:aktivity
P(1M0545)
n3:dodaniDat
n5:2010
n3:domaciTvurceVysledku
n12:1762834
n3:druhVysledku
n15:D
n3:duvernostUdaju
n21:S
n3:entitaPredkladatele
n18:predkladatel
n3:idSjednocenehoVysledku
331549
n3:idVysledku
RIV/00216224:14330/09:00039313
n3:jazykVysledku
n8:eng
n3:klicovaSlova
continuous time games; reachability
n3:klicoveSlovo
n17:continuous%20time%20games n17:reachability
n3:kontrolniKodProRIV
[39C2765C7563]
n3:mistoKonaniAkce
15 12 2009
n3:mistoVydani
Dagstuhl, Germany
n3:nazevZdroje
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009)
n3:obor
n13:IN
n3:pocetDomacichTvurcuVysledku
1
n3:pocetTvurcuVysledku
3
n3:projekt
n20:1M0545
n3:rokUplatneniVysledku
n5:2009
n3:tvurceVysledku
Brázdil, Tomáš Kiefer, Stefan Esparza, Javier
n3:typAkce
n19:WRD
n3:zahajeniAkce
2009-01-01+01:00
s:issn
1868-8969
s:numberOfPages
12
n7:hasPublisher
Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik
n4:isbn
978-3-939897-13-2
n10:organizacniJednotka
14330