Transducing by observing length-reducing and painter rules

Norbert Hundeshagen; Peter Leupold

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2014)

  • Volume: 48, Issue: 1, page 85-105
  • ISSN: 0988-3754

Abstract

top
The recently introduced model of transducing by observing is compared with traditional models for computing transductions on the one hand and the recently introduced restarting transducers on the other hand. Most noteworthy, transducing observer systems with length-reducing rules are almost equivalent to RRWW-transducers. With painter rules we obtain a larger class of relations that additionally includes nearly all rational relations.

How to cite

top

Hundeshagen, Norbert, and Leupold, Peter. "Transducing by observing length-reducing and painter rules." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 48.1 (2014): 85-105. <http://eudml.org/doc/273001>.

@article{Hundeshagen2014,
abstract = {The recently introduced model of transducing by observing is compared with traditional models for computing transductions on the one hand and the recently introduced restarting transducers on the other hand. Most noteworthy, transducing observer systems with length-reducing rules are almost equivalent to RRWW-transducers. With painter rules we obtain a larger class of relations that additionally includes nearly all rational relations.},
author = {Hundeshagen, Norbert, Leupold, Peter},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {restarting automata; computing by observing; transductions},
language = {eng},
number = {1},
pages = {85-105},
publisher = {EDP-Sciences},
title = {Transducing by observing length-reducing and painter rules},
url = {http://eudml.org/doc/273001},
volume = {48},
year = {2014},
}

TY - JOUR
AU - Hundeshagen, Norbert
AU - Leupold, Peter
TI - Transducing by observing length-reducing and painter rules
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2014
PB - EDP-Sciences
VL - 48
IS - 1
SP - 85
EP - 105
AB - The recently introduced model of transducing by observing is compared with traditional models for computing transductions on the one hand and the recently introduced restarting transducers on the other hand. Most noteworthy, transducing observer systems with length-reducing rules are almost equivalent to RRWW-transducers. With painter rules we obtain a larger class of relations that additionally includes nearly all rational relations.
LA - eng
KW - restarting automata; computing by observing; transductions
UR - http://eudml.org/doc/273001
ER -

References

top
  1. [1] A.V. Aho and J.D. Ullman, Properties of Syntax Directed Translations. J. Comput. Syst. Sci.3 (1969) 319–334. Zbl0174.02802MR252130
  2. [2] A.V. Aho and J.D. Ullman,The theory of parsing, translation, and compiling. Prentice-Hall, Inc., Upper Saddle River, NJ, USA (1972). Zbl0264.68032MR408321
  3. [3] R.V. Book and F. Otto, String-rewriting systems. Texts and monographs in computer science. Springer (1993). Zbl0832.68061MR1215932
  4. [4] M. Cavaliere and P. Leupold, Evolution and Observation – A Non-Standard Way to Generate Formal Languages. Theoret. Comput. Sci.321 (2004) 233–248. Zbl1070.68065MR2076146
  5. [5] M. Cavaliere and P. Leupold, Observation of String-Rewriting Systems. Fundam. Inform.74 (2006) 447–462. Zbl1106.68052MR2286857
  6. [6] C. Choffrut and K. Culik II, Properties of Finite and Pushdown Transducers. SIAM J. Comput.12 (1983) 300–315. Zbl0512.68065MR697162
  7. [7] S. Ginsburg and G.F. Rose, Preservation of Languages by Transducers. Inf. Control9 (1966) 153–176. Zbl0186.01301
  8. [8] N. Hundeshagen and P. Leupold, Transducing by Observing, in vol. 263 of NCMA, edited by H. Bordihn, R. Freund, M. Holzer, T. Hinze, M. Kutrib and F. Otto. books@ocg.at, Austrian Computer Society (2010) 85–98. 
  9. [9] N. Hundeshagen and P. Leupold,Transducing by Observing and Restarting Transducers, in vol. 29 of NCMA, edited by R. Freund, M. Holzer, B. Truthe and U. Ultes-Nitsche., books@ocg.at, Österreichische Computer Gesellschaft (2012) 93–106. 
  10. [10] N. Hundeshagen and F. Otto, Characterizing the Rational Functions by Restarting Transducers, in LATA, vol. 7183 of Lect. Notes in Comput. Sci., edited by A.H. Dediu and C. Martín-Vide. Springer (2012) 325–336. Zbl06044353
  11. [11] P. Jancar, F. Mráz, M. Plátek and J. Vogel, Restarting Automata, in FCT, vol. 965 of Lect. Notes in Comput. Sci., edited by H. Reichel. Springer (1995) 283–292. 
  12. [12] P. Jancar, F. Mráz, M. Plátek and J. Vogel, Different Types of Monotonicity for Restarting Automata, in FSTTCS, vol. 1530 of Lect. Notes in Comput. Sci., edited by V. Arvind and R. Ramanujam. Springer (1998) 343–354. Zbl1149.68052
  13. [13] P. Jancar, F. Mráz, M. Plátek and J. Vogel, On Monotonic Automata with a Restart Operation. J. Automata, Languages and Combinatorics 4 (1999) 287–312. Zbl0942.68064MR1737858
  14. [14] F. Otto, Restarting Automata. in vol. 25 of Recent Advances in Formal Languages and Applications, edited by Z. Ésik, C. Martín-Vide, and V. Mitrana. Springer (2006) 269–303. 
  15. [15] G. Rozenberg and A. Salomaa, Handbook of formal languages, word, language, grammar (vol. 1). Springer-Verlag New York, Inc., New York, USA (1997). Zbl0866.68057MR1469992

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.