Thesis icon

Thesis

On collapsible pushdown automata, their graphs and the power of links

Abstract:

Higher-Order Pushdown Automata (HOPDA) are abstract machines equipped with a nested stacks of stacks... of stacks of stacks. Collapsible pushdown automata (CPDA) enhance these stacks with the addition of ‘links’ emanating from atomic elements to the higher-order stacks below. For trees CPDA are equi-expressive with recursion schemes, which can be viewed as simply-typed λY terms. With vanilla HOPDA, one can only capture schemes satisfying a syntactic constraint called safety.

This dis...

Expand abstract

Actions


Access Document


Files:

Authors


More by this author
Institution:
University of Oxford
Oxford college:
Keble College
Department:
Mathematical,Physical & Life Sciences Division - Computing Laboratory
Role:
Author

Contributors

Role:
Supervisor
More from this funder
Funding agency for:
Christopher H. Broadbent
Publication date:
2011
Type of award:
DPhil
Level of award:
Doctoral
URN:
uuid:aaa328fe-60be-4abe-8f84-97dbd9e0a3fe
Local pid:
ora:6265

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP