| Title:
|
Self-reproducing pushdown transducers (English) |
| Author:
|
Meduna, Alexander |
| Author:
|
Lorenc, Luboš |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
41 |
| Issue:
|
4 |
| Year:
|
2005 |
| Pages:
|
[531]-537 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
After a translation of an input string, $x$, to an output string, $y$, a self- reproducing pushdown transducer can make a self-reproducing step during which it moves $y$ to its input tape and translates it again. In this self- reproducing way, it can repeat the translation $n$-times for any $n \ge 1$. This paper demonstrates that every recursively enumerable language can be characterized by the domain of the translation obtained from a self- reproducing pushdown transducer that repeats its translation no more than three times. (English) |
| Keyword:
|
pushdown transducer |
| Keyword:
|
self-reproducing pushdown transduction |
| Keyword:
|
recursively enumerable languages |
| MSC:
|
68Q45 |
| idZBL:
|
Zbl 1249.68104 |
| idMR:
|
MR2180361 |
| . |
| Date available:
|
2009-09-24T20:10:56Z |
| Last updated:
|
2015-03-23 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/135673 |
| . |
| Reference:
|
[1] Harrison M. A.: Introduction to Formal Language Theory.Addison–Wesley, Reading 1978 Zbl 0411.68058, MR 0526397 |
| Reference:
|
[2] Kleijn H. C. M., Rozenberg G.: On the generative power of regular pattern grammars.Acta Inform. 20 (1983), 391–411 Zbl 0541.68048, MR 0732313 |
| Reference:
|
[3] Meduna A.: Automata and Languages: Theory and Applications.Springer, London 2000 Zbl 0951.68056, MR 1778364 |
| Reference:
|
[4] Meduna A.: Simultaneously one-turn two-pushdown automata.Internat. Computer Math. 80 (2003), 679–687 Zbl 1103.68587, MR 1984796, 10.1080/0020716031000070616 |
| Reference:
|
[5] Meduna A., Kolar D.: Regulated pushdown automata.Acta Cybernet. 14 (2000), 653–664 Zbl 1011.68049, MR 1790232 |
| Reference:
|
[6] Revesz G. E.: Introduction to Formal Languages.McGraw–Hill, New York 1983 |
| . |
