Genre
Journal ArticleDate
2016-07-25Author
Beigel, RGasarch, W
Subject
Pushdown AutomataContext free languages
Linear Bounded Automata
Length of description of languages
Permanent link to this record
http://hdl.handle.net/20.500.12613/5706
Metadata
Show full item recordDOI
10.1016/j.tcs.2015.08.028Abstract
© 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.Citation to related work
Elsevier BVHas part
Theoretical Computer ScienceADA compliance
For Americans with Disabilities Act (ADA) accommodation, including help with reading this content, please contact scholarshare@temple.eduae974a485f413a2113503eed53cd6c53
http://dx.doi.org/10.34944/dspace/5688