Hostname: page-component-6898cfcb55-kwdml Total loading time: 0 Render date: 2026-11-11T14:28:57.252Z Has data issue: false hasContentIssue false
  • English
  • Français

Transducing by observing length-reducing and painterrules

Published online by Cambridge University Press:  10 February 2014

Norbert Hundeshagen and
Peter Leupold
Norbert Hundeshagen
Affiliation:
Arbeitsgruppe Theoretische Informatik, Fachbereich Elektrotechnik/Informatik, Universität Kassel, Germany. hundeshagen@theory.informatik.uni-kassel.de
Peter Leupold
Affiliation:
Institut für Informatik, Universität Leipzig, Germany; Peter.Leupold@web.de

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

The recently introduced model of transducing by observing is compared with traditionalmodels for computing transductions on the one hand and the recently introduced restartingtransducers on the other hand. Most noteworthy, transducing observer systems withlength-reducing rules are almost equivalent to RRWW-transducers. With painter rules weobtain a larger class of relations that additionally includes nearly all rationalrelations.

Keywords

Restarting automatacomputing by observingtransductions

References

Aho, A.V. and Ullman, J.D., Properties of Syntax Directed Translations. J. Comput. Syst. Sci. 3 (1969) 319–334. Google Scholar
A.V. Aho and J.D. Ullman,The theory of parsing, translation, and compiling. Prentice-Hall, Inc., Upper Saddle River, NJ, USA (1972).
R.V. Book and F. Otto, String-rewriting systems. Texts and monographs in computer science. Springer (1993).
Cavaliere, M. and Leupold, P., Evolution and Observation – A Non-Standard Way to Generate Formal Languages. Theoret. Comput. Sci. 321 (2004) 233–248. Google Scholar
Cavaliere, M. and Leupold, P., Observation of String-Rewriting Systems. Fundam. Inform. 74 (2006) 447–462. Google Scholar
Choffrut, C. and Culik II, K., Properties of Finite and Pushdown Transducers. SIAM J. Comput. 12 (1983) 300–315. Google Scholar
Ginsburg, S. and Rose, G.F., Preservation of Languages by Transducers. Inf. Control 9 (1966) 153–176. Google Scholar
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.
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.
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.
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.
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.
Jancar, P., Mráz, F., Plátek, M. and Vogel, J., On Monotonic Automata with a Restart Operation. J. Automata, Languages and Combinatorics 4 (1999) 287–312. Google Scholar
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.
G. Rozenberg and A. Salomaa, Handbook of formal languages, word, language, grammar (vol. 1). Springer-Verlag New York, Inc., New York, USA (1997).