Towards a Formal Representation of Interactive Systems

• Autorzy: Banu-Demergian I. T. , Stefanescu G.

Identyfikatory

DOI

10.3233/FI-2014-1017

• Języki publikacji: EN

Abstrakty

EN

Powerful algebraic techniques have been developed for classical sequential computation. Many of them are based on regular expressions and the associated regular algebra. For parallel and interactive computation, extensions to handle 2-dimensional patterns are often required. Finite interactive systems, a 2-dimensional version of finite automata, may be used to recognize 2-dimensional languages. In this paper we present a blueprint for getting a formal representation of parallel, interactive programs and of their semantics. It is based on a recently introduced approach for getting regular expressions for 2-dimensional patterns, particularly using words of arbitrary shapes and powerful control mechanisms on composition. We extend the previously defined class of expressions n2RE with new control features, progressively increasing the expressive power of the formalism up to a level where a procedure for generating the words accepted by finite interactive systems may be obtained. Targeted applications come from the area of modelling, specification, analysis and verification of structured interactive programs via the associated scenario semantics.

Słowa kluczowe

EN

parallel programming; interactive programming; regular expressions; regular algebra; Kleene theorem; network algebra; 2-dimensional languages; finite interactive systems; relational semantics; specification; verification; structured interactive programming

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 131, nr 3-4
• Strony: 313--336
• Opis fizyczny: Bibliogr. 35 poz., rys.

Twórcy

autor

Banu-Demergian I. T.

• Department of Computer Science, University of Bucharest, Romania

autor

Stefanescu G.

• Department of Computer Science, University of Bucharest, Romania

Bibliografia

• [1] Asarin, E., Caspi, P., Maler, O.: Timed regular expressions, Journal of the ACM, 49, 2002, 172–206.
• [2] Banu-Demergian, I. T., Paduraru, C. I., Stefanescu, G.: A new representation of two-dimensional patterns and applications to interactive programming, FSEN 2013, LNCS 8161, 2013.
• [3] Banu-Demergian, I. T., Stefanescu, G.: On the contour representation of two-dimensional patterns, Carpathian Journal Mathematics, 2014 (to appear).
• [4] Bergstra, J., Bethke, I., Ponse, A.: Process algebra with iteration, The Computer Journal, 60, 1994, 109–137.
• [5] Bloom, S., Esik, Z.: Equational axioms for regular sets, Mathematical Structures in Computer Science, 3, 1993, 1–24.
• [6] Bloom, S., Esik, Z.: Iteration Theories: The Equational Logic of Iterative Processes, Springer-Verlag, Berlin, 1993.
• [7] Bonsangue, M., Rutten, J., Silva, A.: A Kleene theorem for polynomial coalgebras, Proc. FSSCS’09, LNCS, Springer-Verlag, 2009.
• [8] Cazanescu, V., Stefanescu, G.: Towards a new algebraic foundation of flowchart scheme theory, Fundamenta Informaticae, 13, 1990, 171–210.
• [9] Cazanescu, V., Stefanescu, G.: Mathematical aspects of natural and formal languages, World Scientific, Singapore, 1995, 43–62.
• [10] Conway, J.: Regular Algebra and Finite Machines, Chapman and Hall, 1971.
• [11] Dragoi, C., Stefanescu, G.: AGAPIA v0. 1: A programming language for interactive systems and its typing system, Electronic Notes in Theoretical Computer Science, 203(3), 2008, 69–94.
• [12] Garg, V., Ragunath, M.: Concurrent regular expressions and their relationship to Petri nets, Theoretical Computer Science, 96, 1992, 285–304.
• [13] Giammarresi, D., Restivo, A.: Two-dimensional languages, in: Handbook of formal languages, Springer, 1997, 215–267.
• [14] Goldin, D., Smolka, S., Wegner, P.: Interactive computation: The new paradigm, Springer, 2006.
• [15] Joyal, A., Street, R., Verity, D.: Traced monoidal categories, Proceedings of the Cambridge Philosophical Society, 119, 1996.
• [16] Kleene, S.: Representation of events in nerve nets and finite automata, Automata Studies, 1956.
• [17] Kozen, D.: A completeness theorem for Kleene algebras and the algebra of regular events, LICS’91, IEEE, 1991.
• [18] Krob, D.: Complete systems of _-rational identities, Theoretical Computer Science, 89, 1991, 207–343.
• [19] Kuich, W., Salomaa, A.: Semirings, automata and languages, Springer-Verlag, Berlin, 1985.
• [20] Latteux,M., Simplot, D.: Context-sensitive string languages and recognizable picture languages, Information and Computation, 138(2), 1997, 160–169.
• [21] Lindgren, K., Moore, C., Nordahl, M.: Complexity of two-dimensional patterns, Journal of statistical physics, 91(5-6), 1998, 909–951.
• [22] Maddux, R.: Relation-algebraic semantics, Theoretical Computer Science, 160(1), 1996, 1–85.
• [23] Manes, E., Arbib, M.: Algebraic approaches to program semantics, Springer-Verlag, Berlin, 1986.
• [24] Matz, O.: Regular Expressions and Context-Free Grammars for Picture Languages, STACS, 1997.
• [25] Milner, R.: Flowgraphs and flow algebras, Journal of the ACM (JACM), 26(4), 1979, 794–818.
• [26] Milner, R.: Action calculi V : Reflexive molecular forms, 1994, Draft, Department of Computer Science, University of Edinburgh.
• [27] Petri, C.: Kommunikation mit automaten, Ph.D. Thesis, 1962.
• [28] Rosenfeld, A.: Picture Languages: Formal Models for Picture Recognition, Academic Press, Inc., Orlando, FL, USA, 1979.
• [29] Salomaa, A.: Two complete axiom systems for the algebra of regular events, Journal of the ACM (JACM), 13(1), 1966, 158–169.
• [30] Sofronia, A., Popa, A., Stefanescu, G.: Undecidability Results for Finite Interactive Systems, Romanian Journal of Information Science and Technology, 12(2), 2009, 265–279, Also: Arxiv, CoRR abs/1001.0143, 2010.
• [31] Stefanescu, G.: Feedback Theories (A Calculus for Isomorphism Classes of Flowchart Schemes)., Number 24 in Preprint Series in Mathematics, INCREST, 1986, Also in: Revue Roumaine de Mathematiques Pures et Applique, 35:73–79, 1990.
• [32] Stefanescu, G.: Network algebra, Springer Verlag, 2000.
• [33] Stefanescu, G.: Algebra of Networks: Modeling simple networks as well as complex interactive systems, in: Proof and System-Reliability, Springer, 2002, 49–78.
• [34] Stefanescu, G.: Interactive Systems: From Folklore to Mathematics, Relmics’01, LNCS 2561, Springer, 2002.
• [35] Stefanescu, G.: Interactive systems with registers and voices, Fundamenta Informaticae, 73(1), 2006, 285–305.