Transducing by observing length-reducing and painter rules
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014) no. 1, pp. 85-105.

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.

DOI : https://doi.org/10.1051/ita/2014002
Classification : 68Q68,  68Q42
Mots clés : restarting automata, computing by observing, transductions
@article{ITA_2014__48_1_85_0,
     author = {Hundeshagen, Norbert and Leupold, Peter},
     title = {Transducing by observing length-reducing and painter rules},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {85--105},
     publisher = {EDP-Sciences},
     volume = {48},
     number = {1},
     year = {2014},
     doi = {10.1051/ita/2014002},
     mrnumber = {3195790},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita/2014002/}
}
Hundeshagen, Norbert; Leupold, Peter. Transducing by observing length-reducing and painter rules. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014) no. 1, pp. 85-105. doi : 10.1051/ita/2014002. http://www.numdam.org/articles/10.1051/ita/2014002/

[1] A.V. Aho and J.D. Ullman, Properties of Syntax Directed Translations. J. Comput. Syst. Sci. 3 (1969) 319-334. | MR 252130 | Zbl 0174.02802

[2] A.V. Aho and J.D. Ullman,The theory of parsing, translation, and compiling. Prentice-Hall, Inc., Upper Saddle River, NJ, USA (1972). | MR 408321

[3] R.V. Book and F. Otto, String-rewriting systems. Texts and monographs in computer science. Springer (1993). | MR 1215932 | Zbl 0832.68061

[4] M. Cavaliere and P. Leupold, Evolution and Observation - A Non-Standard Way to Generate Formal Languages. Theoret. Comput. Sci. 321 (2004) 233-248. | MR 2076146 | Zbl 1070.68065

[5] M. Cavaliere and P. Leupold, Observation of String-Rewriting Systems. Fundam. Inform. 74 (2006) 447-462. | MR 2286857 | Zbl 1106.68052

[6] C. Choffrut and K. Culik Ii, Properties of Finite and Pushdown Transducers. SIAM J. Comput. 12 (1983) 300-315. | MR 697162 | Zbl 0512.68065

[7] S. Ginsburg and G.F. Rose, Preservation of Languages by Transducers. Inf. Control 9 (1966) 153-176. | Zbl 0186.01301

[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] 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] 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.

[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] 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.

[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. | MR 1737858 | Zbl 0942.68064

[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] G. Rozenberg and A. Salomaa, Handbook of formal languages, word, language, grammar (vol. 1). Springer-Verlag New York, Inc., New York, USA (1997). | MR 1469992 | Zbl 0866.68057