×

Maximally parallel contextual string rewriting. (English) Zbl 1367.68152

Lucanu, Dorel (ed.), Rewriting logic and its applications. 11th international workshop, WRLA 2016, held as a satellite event of ETAPS, Eindhoven, The Netherlands, April 2–3, 2016. Revised selected papers. Cham: Springer (ISBN 978-3-319-44801-5/pbk; 978-3-319-44802-2/ebook). Lecture Notes in Computer Science 9942, 152-166 (2016).
Summary: This paper introduces contextual string rewriting as a special kind of parallel string rewriting in which each rule defines a context which is not changed by the application of the rule and can be read (but not modified) by other rules applying concurrently. We study maximal parallel rewriting in this setting and provide a method to encode the computation of a maximally parallel instance for a contextual string rewrite system as a decidable normal form problem for a particular term rewrite system.
For the entire collection see [Zbl 1344.68013].

MSC:

68Q42 Grammars and rewriting systems

Software:

K Prover; Maude
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bottoni, P., Martín-Vide, C., Păun, G., Rozenberg, G.: Membrane systems with promoters/inhibitors. Acta Inform. 38(10), 695–720 (2002) · Zbl 1034.68038 · doi:10.1007/s00236-002-0090-7
[2] Clavel, M., Durán, F., Eker, S., Lincoln, P., Martí-Oliet, N., Meseguer, J., Quesada, J.F.: Maude: specification and programming in rewriting logic. Theor. Comput. Sci. 285(2), 187–243 (2002). doi: 10.1016/S0304-3975(01)00359-0 · Zbl 1001.68059 · doi:10.1016/S0304-3975(01)00359-0
[3] Dinu, A., Dinu, L.P.: A parallel approach to syllabification. In: Gelbukh, A.F. (ed.) CICLing 2005. LNCS, vol. 3406, pp. 83–87. Springer, Heidelberg (2005). doi: 10.1007/978-3-540-30586-6_7 . ISBN 3-540-24523-5 · Zbl 1150.47351 · doi:10.1007/978-3-540-30586-6_7
[4] Dinu, L.P.: On insertion grammars with maximum parallel derivation. Fundam. Inf. 93(4), 357–369 (2009) · Zbl 1177.68134
[5] Galiukschov, B.S.: Semicontextual grammars. In: Matematika Logica i Matematika Linguistika, pp. 38–50. Tallin University (1981)
[6] Hopf, J.-M., Bader, M., Meng, M., Bayer, J.: Is human sentence parsing serial or parallel? Evidence from event-related brain potentials. Cogn. Brain Res. 15(2), 165–177 (2003) · doi:10.1016/S0926-6410(02)00149-0
[7] Kari, L., Thierrin, G.: Contextual insertions, deletions, computability. Inf. Comput. 131(1), 47–61 (1996). ISSN 0890-5401 · Zbl 0872.68038 · doi:10.1006/inco.1996.0091
[8] Levelt, W.J.M., Indefrey, P.: The speaking mind/brain: where do spoken words come from, pp. 77–93 (2000)
[9] Lindenmayer, A., Rozenberg, G. (eds.): Automata, Languages, Development. North-Holland Publishing Co., Amsterdam (1976)
[10] Marcus, S.: Contextual grammars. In: Proceedings of the 1969 Conference on Computational Linguistics, pp. 1–18. Association for Computational Linguistics (1969) · Zbl 0193.32401 · doi:10.3115/990403.990451
[11] Marcus, S.: Contextual grammars and natural languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, pp. 215–235. Springer, Heidelberg (1997) · doi:10.1007/978-3-662-07675-0_5
[12] Meseguer, J.: Rewriting logic as a semantic framework for concurrency: a progress report. In: Sassone, V., Montanari, U. (eds.) CONCUR 1996. LNCS, vol. 1119, pp. 331–372. Springer, Heidelberg (1996). ISBN 3-540-61604-7 · doi:10.1007/3-540-61604-7_64
[13] Mitchell, T.M.: Machine Learning, vol. 45, p. 995. McGraw Hill, Burr Ridge (1997) · Zbl 0913.68167
[14] Păun, G.: Computing with membranes. J. Comput. Syst. Sci. 61(1), 108–143 (2000) · Zbl 0956.68055 · doi:10.1006/jcss.1999.1693
[15] Prusinkiewicz, P., Lindenmayer, A.: The Algorithmic Beauty of Plants. Springer Science & Business Media, New York (2012) · Zbl 0850.92038
[16] Roşu, G., Şerbănuţă, T.F.: An overview of the \[ \mathbb{K} \] semantic framework. J. Log. Algebr. Program. 79(6), 397–434 (2010) · Zbl 1214.68188 · doi:10.1016/j.jlap.2010.03.012
[17] Visser, E., Benaissa, Z.A., Tolmach, A.: Building program optimizers with rewriting strategies. In: Proceedings of the Third ACM SIGPLAN International Conference on Functional Programming, ICFP 1998, pp. 13–26. ACM, New York (1998). doi: 10.1145/289423.289425 . ISBN 1-58113-024-4. http://doi.acm.org/10.1145/289423.289425 · Zbl 1369.68084 · doi:10.1145/289423.289425
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.