About: On the memory consumption of probabilistic pushdown automata

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: On the memory consumption of probabilistic pushdown automata Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
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. (en)
Title	On the memory consumption of probabilistic pushdown automata On the memory consumption of probabilistic pushdown automata (en)
skos:prefLabel	On the memory consumption of probabilistic pushdown automata On the memory consumption of probabilistic pushdown automata (en)
skos:notation	RIV/00216224:14330/09:00039313!RIV10-MSM-14330___
http://linked.open...avai/riv/aktivita	P
http://linked.open...avai/riv/aktivity	P(1M0545)
http://linked.open...vai/riv/dodaniDat	2010
http://linked.open...aciTvurceVysledku	Brázdil, Tomáš
http://linked.open.../riv/druhVysledku	D - Článek ve sborníku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Masarykova univerzita / Fakulta informatiky
http://linked.open...dnocenehoVysledku	331549
http://linked.open...ai/riv/idVysledku	RIV/00216224:14330/09:00039313
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	continuous time games; reachability (en)
http://linked.open.../riv/klicoveSlovo	continuous time games reachability
http://linked.open...ontrolniKodProRIV	[39C2765C7563]
http://linked.open...v/mistoKonaniAkce	15 12 2009
http://linked.open...i/riv/mistoVydani	Dagstuhl, Germany
http://linked.open...i/riv/nazevZdroje	IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009)
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	3 (xsd:int)
http://linked.open...vavai/riv/projekt	Institute for Theoretical Computer Science
http://linked.open...UplatneniVysledku	2009
http://linked.open...iv/tvurceVysledku	Brázdil, Tomáš Kiefer, Stefan Esparza, Javier
http://linked.open...vavai/riv/typAkce	WRD - Světová
http://linked.open.../riv/zahajeniAkce	2009-01-01 (xsd:date)
issn	1868-8969
number of pages	12 (xsd:int)
http://purl.org/ne...btex#hasPublisher	Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik
https://schema.org/isbn	978-3-939897-13-2
http://localhost/t...ganizacniJednotka	14330

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 47 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software