This item is non-discoverable
Loading...
Non-discoverable
On the sizes of DPDAs, PDAs, LBAs
Beigel, R Gasarch, W
Beigel, R
Gasarch, W
Citations
Altmetric:
Genre
Journal Article
Date
2016-07-25
Advisor
Committee member
Group
Department
Permanent link to this record
Collections
Research Projects
Organizational Units
Journal Issue
DOI
10.1016/j.tcs.2015.08.028
Abstract
© 2015. There are languages A such that there is a Pushdown Automata (PDA) that recognizes A which is much smaller than any Deterministic Pushdown Automata (DPDA) that recognizes A. There are languages A such that there is a Linear Bounded Automata (Linear Space Turing Machine, henceforth LBA) that recognizes A which is much smaller than any PDA that recognizes A. There are languages A such that both A and A are recognizable by a PDA, but the PDA for A is much smaller than the PDA for A. There are languages A1, A2 such that A1, A2, A1∩A2 are recognizable by a PDA, but the PDA for A1 and A2 are much smaller than the PDA for A1∩A2. We investigate these phenomena and show that, in all these cases, the size difference is captured by a function whose Turing degree is on the second level of the arithmetic hierarchy.Our theorems lead to infinitely-many-n results. For example: for-infinitely-many-n there exists a language An recognized by a DPDA such that there is a small PDA for An, but any DPDA for An is very large. We look at cases where we can get all-but-a-finite-number-of-n results, though with much smaller size differences.
Description
Citation
Citation to related work
Elsevier BV
Has part
Theoretical Computer Science
ADA compliance
For Americans with Disabilities Act (ADA) accommodation, including help with reading this content, please contact scholarshare@temple.edu