Sequential monotonicity for restarting automata

Tomasz Jurdziński; Friedrich Otto

RAIRO - Theoretical Informatics and Applications (2007)

  • Volume: 41, Issue: 2, page 157-175
  • ISSN: 0988-3754

Abstract

top
As already 2-monotone R-automata accept NP-complete languages, we introduce a restricted variant of j-monotonicity for restarting automata, called sequential j-monotonicity. For restarting automata without auxiliary symbols, this restricted variant still yields infinite hierarchies. However, for restarting automata with auxiliary symbols, all degrees of sequential monotonicity collapse to the first level, implying that RLWW-automata that are sequentially monotone of degree j for any j ≥ 1 only accept context-free languages.

How to cite

top

Jurdziński, Tomasz, and Otto, Friedrich. "Sequential monotonicity for restarting automata." RAIRO - Theoretical Informatics and Applications 41.2 (2007): 157-175. <http://eudml.org/doc/250060>.

@article{Jurdziński2007,
abstract = { As already 2-monotone R-automata accept NP-complete languages, we introduce a restricted variant of j-monotonicity for restarting automata, called sequential j-monotonicity. For restarting automata without auxiliary symbols, this restricted variant still yields infinite hierarchies. However, for restarting automata with auxiliary symbols, all degrees of sequential monotonicity collapse to the first level, implying that RLWW-automata that are sequentially monotone of degree j for any j ≥ 1 only accept context-free languages. },
author = {Jurdziński, Tomasz, Otto, Friedrich},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Restarting automaton; sequential monotonicity; hierarchies; -monotonicity},
language = {eng},
month = {7},
number = {2},
pages = {157-175},
publisher = {EDP Sciences},
title = {Sequential monotonicity for restarting automata},
url = {http://eudml.org/doc/250060},
volume = {41},
year = {2007},
}

TY - JOUR
AU - Jurdziński, Tomasz
AU - Otto, Friedrich
TI - Sequential monotonicity for restarting automata
JO - RAIRO - Theoretical Informatics and Applications
DA - 2007/7//
PB - EDP Sciences
VL - 41
IS - 2
SP - 157
EP - 175
AB - As already 2-monotone R-automata accept NP-complete languages, we introduce a restricted variant of j-monotonicity for restarting automata, called sequential j-monotonicity. For restarting automata without auxiliary symbols, this restricted variant still yields infinite hierarchies. However, for restarting automata with auxiliary symbols, all degrees of sequential monotonicity collapse to the first level, implying that RLWW-automata that are sequentially monotone of degree j for any j ≥ 1 only accept context-free languages.
LA - eng
KW - Restarting automaton; sequential monotonicity; hierarchies; -monotonicity
UR - http://eudml.org/doc/250060
ER -

References

top
  1. J. Berstel. Transductions and Context-Free Languages. Teubner, Stuttgart (1979).  
  2. R.V. Book and F. Otto, String-Rewriting Systems. Springer, New York (1993).  Zbl0832.68061
  3. R. Cremanns and F. Otto, The language of final stack contents of a pushdown automaton is effectively regular. Mathematische Schriften Kassel 11/93, Universität Kassel (1993).  
  4. S. Greibach, A note on pushdown store automata and regular systems. Proc. Amer. Math. Soc.18 (1967) 263–268.  Zbl0183.01703
  5. P. Jančar, F. Mráz, M. Plátek and J. Vogel. Restarting automata, in FCT'95, Proc., edited by H. Reichel, Springer, Berlin. Lect. Notes Comput. Sci.965 (1995) 283–292.  Zbl1149.68052
  6. P. Jančar, F. Mráz, M. Plátek and J. Vogel, On monotonic automata with a restart operation. J. Autom. Lang. Comb.4 (1999) 287–311.  Zbl0942.68064
  7. T. Jurdziński, K. Loryś, G. Niemann and F. Otto, Some results on RWW- and RRWW-automata and their relation to the class of growing context-sensitive languages. J. Autom. Lang. Comb.9 (2004) 407–437.  Zbl1083.68057
  8. T. Jurdziński, F. Otto, F. Mráz and M. Plátek, On the complexity of 2-monotone restarting automata, in DLT 2004, Proc., edited by C.S. Calude, E. Calude and M.J. Dinneen, Springer, Berlin. Lect. Notes Comput. Sci.3340 (2004) 237–248.  Zbl1117.68404
  9. T. Jurdziński, F. Mráz, F. Otto and M. Plátek, Degrees of non-monotonicity for restarting automata. Theoret. Comput. Sci.369 (2006) 1–34.  Zbl1142.68423
  10. G. Niemann and F. Otto, Further results on restarting automata, in Words, Languages and Combinatorics III, Proc., edited by M. Ito and T. Imaoka. World Scientific, Singapore (2003) 352–369.  
  11. K. Oliva, P. Květoň and R. Ondruška, The computational complexity of rule-based part-of-speech tagging, in TSD 2003, Proc., edited by V. Matousek and P. Mautner, Springer, Berlin. Lect. Notes Comput. Sci.2807 (2003) 82–89.  
  12. F. Otto, Restarting automata and their relations to the Chomsky hierarchy, in Developments in Language Theory, Proc. DLT'2003, edited by Z. Esik and Z. Fülöp, Springer, Berlin. Lect. Notes Comput. Sci.2710 (2003) 55–74.  Zbl1037.68088
  13. F. Otto, Restarting Automata, in Recent Advances in Formal Languages and Applications, Z. Ésik, C. Martin-Vide and V. Mitrana (Eds.), Springer, Berlin. Stud. Comput. Intelligence25 (2006) 269–303.  
  14. M. Plátek, Two-way restarting automata and j-monotonicity, in Theory and Practice of Informatics, Proc. SOFSEM 2001, edited by L. Pacholski and P. Ružička, Springer-Verlag, Berlin. Lect. Notes Comput. Sci.2234 (2001) 316–325.  
  15. M. Plátek and F. Mráz, Degrees of (non)monotonicity of RRW-automata, in Preproceedings of the 3rd Workshop on Descriptional Complexity of Automata, Grammars and Related Structures, Report No. 16, edited by J. Dassow and D. Wotschke, Fakultät für Informatik, Universität Magdeburg (2001) 159–165.  
  16. M. Plátek, M. Lopatková and K. Oliva, Restarting automata: motivations and applications. In Workshop `Petrinetze' and 13. Theorietag `Formale Sprachen und Automaten', Proc., edited by M. Holzer, Institut für Informatik, Technische Universität München (2003) 90–96.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.