Please use this identifier to cite or link to this item: http://dx.doi.org/10.18419/opus-2593
Full metadata record
DC FieldValueLanguage
dc.contributor.authorSuwimonteerabuth, Dejvuthde
dc.contributor.authorSchwoon, Stefande
dc.contributor.authorEsparza, Javierde
dc.date.accessioned2006-12-18de
dc.date.accessioned2016-03-31T07:58:40Z-
dc.date.available2006-12-18de
dc.date.available2016-03-31T07:58:40Z-
dc.date.issued2006de
dc.identifier.other262849380de
dc.identifier.urihttp://nbn-resolving.de/urn:nbn:de:bsz:93-opus-29054de
dc.identifier.urihttp://elib.uni-stuttgart.de/handle/11682/2610-
dc.identifier.urihttp://dx.doi.org/10.18419/opus-2593-
dc.description.abstractMotivated by recent applications of pushdown systems to computer security problems, we present an efficient algorithm for the reachability problem of alternating pushdown systems. Although the algorithm is exponential, a careful analysis reveals that the exponent is usually small in typical applications. We show that the algorithm can be used to compute winning regions in pushdown games. In a second contribution, we observe that the algorithm runs in polynomial time for a certain subproblem, and show that the computation of certificate chains with threshold certificates in the SPKI/SDSI authorization framework can be reduced to this subproblem. We present a detailed complexity analysis of the algorithm and its application, and report on experimental results obtained with a prototype implementation.en
dc.language.isoende
dc.relation.ispartofseriesTechnischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik;2006,9de
dc.rightsinfo:eu-repo/semantics/openAccessde
dc.subject.classificationComputersicherheit , Algorithmus , Berechnungskomplexitätde
dc.subject.ddc004de
dc.subject.otherpushdown systems , reachability problem , algorithmen
dc.titleEfficient algorithms for alternating pushdown systems : application to certificate chain discovery with threshold subjectsen
dc.typeworkingPaperde
dc.date.updated2013-07-09de
ubs.fakultaetFakultät Informatik, Elektrotechnik und Informationstechnikde
ubs.institutInstitut für Formale Methoden der Informatikde
ubs.opusid2905de
ubs.publikation.typArbeitspapierde
ubs.schriftenreihe.nameTechnischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnikde
Appears in Collections:05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Files in This Item:
File Description SizeFormat 
TR_2006_09.pdf252,77 kBAdobe PDFView/Open


Items in OPUS are protected by copyright, with all rights reserved, unless otherwise indicated.