Document
Services
BibSonomy
CiteUlike
Connotea
Del.icio.us
Digg
Facebook
|
|||||||||||||||
Theoret. Informatics Appl. 39, 325-342 (2005)
DOI: 10.1051/ita:2005021
Hierarchies of weakly monotone restarting automata
Frantisek Mráz1 and Friedrich Otto21 Department of Computer Science, Charles University, Malostranské nám. 25, 118 00 Praha 1, Czech Republic; mraz@ksvi.ms.mff.cuni.cz
2 Fachbereich Mathematik/Informatik, Universität Kassel, 34109 Kassel, Germany; otto@theory.informatik.uni-kassel.de
(Received June 11, 2003. Accepted May 5, 2004.)
Abstract
It is known that the weakly monotone restarting automata accept
exactly the growing context-sensitive languages. We introduce a
measure on the degree of weak monotonicity and show that the
language classes obtained in this way form strict hierarchies for
the various types of deterministic and nondeterministic restarting
automata without auxiliary symbols.
Mathematics Subject Classification. 68Q10, 68Q42, 68Q45
Key words: Restarting automata -- weak monotonicity -- hierarchies
© EDP Sciences 2005
| What is OpenURL? |
The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.
- If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
- You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
- You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.