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 : 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://archive.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://archive.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://archive.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://archive.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 | Zbl

[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

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

[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 | Zbl

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

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

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

[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 | Zbl

[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 | Zbl

Cité par Sources :