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
Division:
MPLS
Department:
Computer Science
Oxford college:
Keble College
Role:
Author
More by this author
Division:
MPLS
Department:
Computer Science
Role:
Author

Contributors

Division:
MPLS
Department:
Computer Science
Role:
Supervisor
More from this funder
Funding agency for:
Broadbent, C
Publication date:
2011
Type of award:
DPhil
Level of award:
Doctoral
Awarding institution:
University of Oxford
Language:
English
Keywords:
Subjects:
UUID:
uuid:aaa328fe-60be-4abe-8f84-97dbd9e0a3fe
Local pid:
ora:6265
Deposit date:
2012-05-30

Terms of use


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