2014 | OriginalPaper | Chapter
Oracle Pushdown Automata, Nondeterministic Reducibilities, and the Hierarchy over the Family of Context-Free Languages
Author : Tomoyuki Yamakami
Published in: SOFSEM 2014: Theory and Practice of Computer Science
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We implement various oracle mechanisms on nondeterministic pushdown automata, which naturally induce nondeterministic reducibilities among formal languages in a theory of context-free languages. In particular, we examine a notion of nondeterministic many-one CFL-reducibility and carry out ground work of formulating a coherent framework for further expositions. Another more powerful reducibility—Turing CFL-reducibility—is also discussed in comparison. The Turing CFL-reducibility, in particular, makes it possible to induce a useful hierarchy (the CFL hierarchy) built over the family CFL of context-free languages. For each level of this hierarchy, basic structural properties are proven and three alternative characterizations are presented. We also show that the CFL hierarchy enjoys an upward collapse property. The first and second levels of the hierarchy are proven to be different. We argue that the CFL hierarchy coincides with a hierarchy over CFL built by applications of many-one CFL-reductions. Our goal is to provide a solid foundation for structural-complexity analyses in automata theory.