Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

A parallel context-free derivation hierarchy

Klaus ReinhardtContact Information

(6)  Wilhelm-Schickhard Institut für Informatik, Universität Tübingen, Sand 13, D-72076 Tübingen, Germany
Abstract
We consider the number of parallel derivation steps as complexity measure for context-free languages and show that a strict and dense hierarchy is obtained between logarithmic and linear (arbitrary) tree height. We hereby improve a result of Gabarro. Furthermore we give a non-regular language with logarithmic tree height disproving a conjecture of Culik and Maurer. As a new method we use counter-representations, where the successor relation can be handled as the complement of context-free languages.
Article  This research has been partially supported by the DFG Project La 618/3-2 KOMET.

Contact Information Klaus Reinhardt
Email: reinhard@informatik.uni-tuebingen.de
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.105 • Server: mpweb06
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)