158
views
0
recommends
+1 Recommend
1 collections
    4
    shares
      • Record: found
      • Abstract: found
      • Conference Proceedings: found
      Is Open Access

      Computing Transitive Closures of Hedge Transformations

      First International Workshop on Verification and Evaluation of Computer and Communication Systems (VECoS 2007) (VECOS)

      Verification and Evaluation of Computer and Communication Systems

      5-6 May 2007

      Model-checking, Regular model-checking, Rewriting systems, Hedge automata, Transitive closures, Reachability set

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          We consider the framework of regular hedge model checking where configurations are represented by trees of arbitrary arities, sets of configurations are represented by regular hedge automata, and the dynamic of a system is modeled by a term rewriting system. We consider the problem of computing the transitive closure R*(L) of a hedge automaton L and a (not necessarily structure preserving) term rewriting system R. This construction is not possible in general. Therefore, we present a semi-algorithm that computes, in case of termination, an over-approximation of this reachability set. We show that our procedure computes the exact reachability set in many practical applications. We have successfully applied our technique to compute transitive closures for some mutual exclusion protocols defined on arbitrary width tree topologies, as well as for two interesting XML applications.

          Related collections

          Most cited references 11

          • Record: found
          • Abstract: not found
          • Article: not found

          Macro tree transducers

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Symbolic model checking with rich assertional languages

              Bookmark
              • Record: found
              • Abstract: not found
              • Book Chapter: not found

              Iterating Transducers in the Large

                Bookmark

                Author and article information

                Contributors
                Conference
                May 2007
                May 2007
                : 1-15
                Affiliations
                LIAFA, CNRS & University of Paris 7, Paris, France.
                Article
                10.14236/ewic/VECOS2007.7
                © Tayssir Touili et al. Published by BCS Learning and Development Ltd. First International Workshop on Verification and Evaluation of Computer and Communication Systems (VECoS 2007), Algiers, Algeria

                This work is licensed under a Creative Commons Attribution 4.0 Unported License. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

                First International Workshop on Verification and Evaluation of Computer and Communication Systems (VECoS 2007)
                VECOS
                1
                Algiers, Algeria
                5-6 May 2007
                Electronic Workshops in Computing (eWiC)
                Verification and Evaluation of Computer and Communication Systems
                Product
                Product Information: 1477-9358BCS Learning & Development
                Self URI (journal page): https://ewic.bcs.org/
                Categories
                Electronic Workshops in Computing

                Comments

                Comment on this article