Context-free event domains are recognizable. (English) Zbl 0928.68050
Summary: The possibly non-distributive event domains which arise from Winskel’s event structures with binary conflict are known to coincide with the domains of configurations of Stark’s trace automata. We prove that whenever the transitive reduction of the order on finite elements in an event domain is a context-free graph in the sense of Müller and Schupp, the event domain may also be generated from a finite trace automaton, where both the set of states and the concurrent alphabet are finite. We show that the set of graph grammars which generate event domains is a recursive set. We obtain altogether an effective procedure which decides from an unlabeled graph grammar whether it generates an event domain and which constructs in that case a finite trace automaton recognizing that event domain. \(\copyright\) Academic Press.
MSC:
| 68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |
Keywords:
Stark’s trace automataReferences:
| [1] | Baeten, J. C.M; Bergstra, J. A.; Klop, J. W., On the consistency of Koomen’s fair abstraction rule, Theoret. Comput. Sci., 51, 129-176 (1987) · Zbl 0621.68010 |
| [2] | Baeten, J. C.M; Bergstra, J. A.; Klop, J. W., Decidability of bisimulation equivalence for processes generating context-free languages, J. Assoc. Comput. Mach., 40, 653-682 (1993) · Zbl 0801.68102 |
| [3] | Badouel, E.; Darondeau, P., Trace nets. REX workshop, Semantics: Foundation and Application. Semantics: Foundation and Application, Lecture Notes in Computer Science, 666 (1993), Springer-Verlag: Springer-Verlag Berlin/New York, p. 21-50 |
| [4] | Bednarczyk, M., Categories of Asynchronous System (1987), University of Sussex |
| [5] | Berge, C. Graphes et hypergraphes, Dunod, Paris; Berge, C. Graphes et hypergraphes, Dunod, Paris · Zbl 0213.25702 |
| [6] | Boudol, G.; Castellani, I., Flow models of distributed computations: Three equivalent semantics for CCS, Inform. and Comput., 114, 247-314 (1994) · Zbl 0938.68715 |
| [7] | Büchi, J. R., On a decision method in restricted second order arithmetic, Proceedings, International Congress on Logic, Methodology and Philosophy of Science (1960), Stanford Univ. Press: Stanford Univ. Press Stanford, p. 1-11 · Zbl 0147.25103 |
| [8] | Caucal, D., On the regular structure of prefix rewriting, Theoret. Comput. Sci., 106, 61-86 (1992) · Zbl 0780.68077 |
| [9] | Courcelle, B., Graph rewriting: An algebraic and logic approach, (v. Leeuwen, J., Handbook of Theoretical Computer Science (1990), Elsevier: Elsevier Amsterdam), 193-242 · Zbl 0900.68282 |
| [10] | Curien, P. L., Categorical Combinators, Sequential Algorithms and Functional Programming. Categorical Combinators, Sequential Algorithms and Functional Programming, Research notes in Theoretical Computer Science (1986), Pitman: Pitman London · Zbl 0643.68004 |
| [11] | de Simone, R., Calculabilité et expressivité dans l’algèbre de processus MEIJE (1984) |
| [12] | Goltz, U.; Loogen, R., Modelling nondeterministic concurrent processes with event structures, Fund. Inform., XIV, 39-74 (1991) · Zbl 0717.68028 |
| [13] | Herwig, B., Extending partial isomorphisms on finite structures, Combinatorica, 15, 365-371 (1995) · Zbl 0830.05037 |
| [14] | Hrushovski, E., Extending partial isomorphisms of graphs, Combinatorica, 12, 411-416 (1992) · Zbl 0767.05053 |
| [15] | Lascar, D. A note on a theorem of Hrushovski, 1994, lascar@logique.jussieu.fr.; Lascar, D. A note on a theorem of Hrushovski, 1994, lascar@logique.jussieu.fr. |
| [16] | Mukund, M.; Thiagarajan, P. S., A logical characterization of well branching event structures, Theoret. Comput. Sci., 96, 35-72 (1992) · Zbl 0761.68058 |
| [17] | Müller, D.; Schupp, P., The theory of ends, pushdown automata, and second order logic, Theoret. Comput. Sci., 37, 51-75 (1985) · Zbl 0605.03005 |
| [18] | Nielsen, M.; Plotkin, G.; Winskel, G., Petri nets, event structures and domains, Part I, Theoret. Comput. Sci., 13, 85-108 (1981) · Zbl 0452.68067 |
| [19] | Nielsen, M.; Winskel, G., Categories of models for concurrency, (Abramsky, S.; Gabbay, D. M.; Maibaum, T. S.E, Handbook of Logic in Computer Science (1995), Oxford Univ. Press: Oxford Univ. Press Oxford), 1-148 · Zbl 0876.68001 |
| [20] | Penczek, W., A temporal logic for event structures, Fund. Inform., 11, 297-326 (1988) · Zbl 0677.03012 |
| [21] | Schmitt, V., Réprésentations finies de comportements concurrents (1997), Université de Rennes 1 |
| [22] | Smyth, M. B., Effectively given domains, Theoret. Comput. Sci., 5, 257-274 (1977) · Zbl 0429.03028 |
| [23] | Stark, E. W., Connections between a concrete and an abstract model of concurrent systems, 5th Mathematical Foundations of Programming Semantics (1989), p. 53-79 · Zbl 1509.68190 |
| [24] | Stark, E. W., Compositional relational semantics for indeterminate dataflow networks, Summer Conference on Category Theory and Computer Science. Summer Conference on Category Theory and Computer Science, Lecture Notes in Computer Science, 389 (1989), Springer-Verlag: Springer-Verlag Berlin/New York, p. 52-74 · Zbl 1493.68199 |
| [25] | Vaandrager, F. W., Expressiveness results for process algebras, REX Workshop “Semantics: Foundation and Application. REX Workshop “Semantics: Foundation and Application, Lecture Notes in Computer Science, 666 (1992), Springer-Verlag: Springer-Verlag Berlin/New York |
| [26] | Winskel, G., Events in Computations (1980), University of Edinburgh |
| [27] | Winskel, G., An introduction to event structures, REX School “Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency. REX School “Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency, Lecture Notes in Computer Science, 354 (1988), Springer-Verlag: Springer-Verlag Berlin/New York, p. 364-397 · Zbl 0683.68074 |
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.
