Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorSuwimonteerabuth, Dejvuthde
dc.contributor.authorSchwoon, Stefande
dc.contributor.authorEsparza, Javierde
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.relation.ispartofseriesTechnischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik;2006,9de
dc.subject.classificationComputersicherheit , Algorithmus , Berechnungskomplexitätde
dc.subject.otherpushdown systems , reachability problem , algorithmen
dc.titleEfficient algorithms for alternating pushdown systems : application to certificate chain discovery with threshold subjectsen
ubs.fakultaetFakultät Informatik, Elektrotechnik und Informationstechnikde
ubs.institutInstitut für Formale Methoden der Informatikde
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.