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.
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/}
}
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 SP - 85 EP - 105 VL - 48 IS - 1 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita/2014002/ DO - 10.1051/ita/2014002 LA - en ID - ITA_2014__48_1_85_0 ER -
%0 Journal Article %A Hundeshagen, Norbert %A Leupold, Peter %T Transducing by observing length-reducing and painter rules %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2014 %P 85-105 %V 48 %N 1 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita/2014002/ %R 10.1051/ita/2014002 %G en %F 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) no. 1, pp. 85-105. doi : 10.1051/ita/2014002. http://www.numdam.org/articles/10.1051/ita/2014002/
[1] and , Properties of Syntax Directed Translations. J. Comput. Syst. Sci. 3 (1969) 319-334. | MR | Zbl
[2] and ,The theory of parsing, translation, and compiling. Prentice-Hall, Inc., Upper Saddle River, NJ, USA (1972). | MR
[3] and , String-rewriting systems. Texts and monographs in computer science. Springer (1993). | MR | Zbl
[4] and , Evolution and Observation - A Non-Standard Way to Generate Formal Languages. Theoret. Comput. Sci. 321 (2004) 233-248. | MR | Zbl
[5] and , Observation of String-Rewriting Systems. Fundam. Inform. 74 (2006) 447-462. | MR | Zbl
[6] and , Properties of Finite and Pushdown Transducers. SIAM J. Comput. 12 (1983) 300-315. | MR | Zbl
[7] and , Preservation of Languages by Transducers. Inf. Control 9 (1966) 153-176. | Zbl
[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.
[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 | Zbl
[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 | Zbl
Cité par Sources :
