Observation of String-Rewriting Systems

• Autorzy: Cavaliere M. , Leupold P.
• Języki publikacji: EN

Abstrakty

EN

Models of computation in theoretical computer science very frequently consist of a device performing some type of process, like a Turing machine and its computation or a grammar and its derivation. After the process halts, only some final output is regarded as the result. In adding an observer to such a device, one can obtain a protocol of the entire process and then use this as the result of the computation. In several recent articles this approach has proved to often exceed greatly the power of the observed system. Here we apply this architecture to string-rewriting systems. They receive a string as input, and a combination of observer and decider then determines whether this string is accepted. This decision is based only on the rewriting process performed. First we determine the power of painter, context-free, and inverse context-free rewriting systems in terms of McNaughton languages. Then these are investigated as components of rewriting/observer systems, and we obtain characterizations of the classes of context-sensitive and recursively enumerable languages. Finally we investigate some limitations, i.e. characterize some systems, where observation does not increase power.

Słowa kluczowe

EN

string-rewriting; McNaughton languages; observation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 74, nr 4
• Strony: 447--462
• Opis fizyczny: bibliogr. 15 poz.

Twórcy

autor

Cavaliere M.

autor

Leupold P.

• Research Group on Mathematical Linguistics Pca. Imperial Tarraco 43005 Tarragona,Catalunya, Espana,

Bibliografia

• [1] J.P. ALLOUCHE and J. SHALLIT: Automatic Sequences. Cambridge University Press, Cambridge, 2003.
• [2] M. BEAUDRY,M. HOLZER, G. NIEMANN and F. OTTO: McNaughton families of languages. In: Theoretical Computer Science 290, 2003, pp. 1581-1628.
• [3] J. BERSTEL: Transductions and Context-Free Languages. Teubner, Stuttgart, 1979.
• [4] R. BOOK and F. OTTO: String-Rewriting Systems. Springer, Berlin, 1988.
• [5] M. CAVALIERE and P. LEUPOLD: Evolution and Observation - A new way to look at Membrane Systems. In: Membrane Computing, InternationalWorkshop,WMC 2003. Lecture Notes in Computer Science 2933, Springer-Verlag, Berlin, 2004, pp. 70-87.
• [6] M. CAVALIERE and P. LEUPOLD: Evolution and Observation - A Non-StandardWay to Generate Formal Languages. In: Theoretical Computer Science 321, 2004, pp. 233-248.
• [7] M. CAVALIERE and P. LEUPOLD: Evolution and Observation - A Non-Standard Way to Accept Formal Languages. In: MCU 2004, Lecture Notes in Computer Science 3354, Springer-Verlag, Berlin, 2005, pp. 152-162.
• [8] M.A. HARRISON: Introduction to Formal Language Theory. Reading, Mass., 1978.
• [9] D. HOFBAUER and J. WALDMANN: Deleting String-Rewriting Systems preserve regularity. In: Theoretical Computer Science 327, 2004, pp. 301-317.
• [10] L. ILIE and A. SALOMAA: 2-Testability and Relabelings Produce Everything. In: Journal of Computer and System Sciences 56(3), 1998, pp. 253-262.
• [11] P. LEUPOLD: Non-Universal Grammar/Observer Systems. Manuscript.
• [12] R. MCNAUGHTON, P. NARENDRAN and F. OTTO: Church-Rosser Thue systems and formal languages. In: Journal of the ACM 35, 1988, pp. 324-344.
• [13] GH. PǍUN, G. ROZENBERG and A. SALOMAA: DNA Computing - New Computing Paradigms. Springer Verlag, Berlin, 1998.
• [14] A. SALOMAA : Formal Languages. Academic Press, Orlando, 1973.
• [15] J.R. WOINOWSKI: The Context-Splittable Normal Form For Church Rosser Language Systems. In: Information and Control 183, 2003, pp. 245-274.