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.
@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},
volume = {48},
year = {2014},
pages = {85-105},
doi = {10.1051/ita/2014002},
mrnumber = {3195790},
language = {en},
url = {http://dml.mathdoc.fr/item/ITA_2014__48_1_85_0}
}
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) pp. 85-105. doi : 10.1051/ita/2014002. http://gdmltest.u-ga.fr/item/ITA_2014__48_1_85_0/
[1] and , Properties of Syntax Directed Translations. J. Comput. Syst. Sci. 3 (1969) 319-334. | MR 252130 | Zbl 0174.02802
[2] and ,The theory of parsing, translation, and compiling. Prentice-Hall, Inc., Upper Saddle River, NJ, USA (1972). | MR 408321
[3] and , String-rewriting systems. Texts and monographs in computer science. Springer (1993). | MR 1215932 | Zbl 0832.68061
[4] and , Evolution and Observation - A Non-Standard Way to Generate Formal Languages. Theoret. Comput. Sci. 321 (2004) 233-248. | MR 2076146 | Zbl 1070.68065
[5] and , Observation of String-Rewriting Systems. Fundam. Inform. 74 (2006) 447-462. | MR 2286857 | Zbl 1106.68052
[6] and , Properties of Finite and Pushdown Transducers. SIAM J. Comput. 12 (1983) 300-315. | MR 697162 | Zbl 0512.68065
[7] and , Preservation of Languages by Transducers. Inf. Control 9 (1966) 153-176. | Zbl 0186.01301
[8] and , 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] and ,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] and , 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. | Zbl pre06044353
[11] , , and , Restarting Automata, in FCT, vol. 965 of Lect. Notes in Comput. Sci., edited by H. Reichel. Springer (1995) 283-292.
[12] , , and , 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] , , and , On Monotonic Automata with a Restart Operation. J. Automata, Languages and Combinatorics 4 (1999) 287-312. | MR 1737858 | Zbl 0942.68064
[14] , 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] and , Handbook of formal languages, word, language, grammar (vol. 1). Springer-Verlag New York, Inc., New York, USA (1997). | MR 1469992 | Zbl 0866.68057