×

Progressive solutions to a parallel automata equation. (English) Zbl 1100.68047

Summary: We consider the problem of deriving a component \(X\) of a system knowing the behavior of the whole system \(C\) and the other components \(A\). The component \(X\) is derived by solving the parallel automata equation \(A \diamondsuit X \cong C\). We present an algorithm for deriving a largest progressive solution to the equation that combined with \(A\) does not block any possible action in \(C\) and we establish conditions that allow us to characterize all progressive solutions.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barrett, G.; Lafortune, S., Bisimulation, the supervisory control problem, and strong model matching for finite state machines, Discrete Event Dynamic Systems: Theory Appl., 8, 4, 377-429 (1998) · Zbl 0919.93005
[2] Bochmann, G.v.; Merlin, P. M., On the construction of communication protocols, ICCC, 1980, pp. 371-378, reprinted, (Sunshine, C., Communication Protocol Modeling (1981), Artech House: Artech House Norwood, MA)
[3] Buffalov, S.; El-Fakih, K.; Yevtushenko, N.; Bochmann, G.v., Progressive solutions for a parallel automata equation, (Proc. IFIP 23rd Internat. Conf. on Formal Techniques for Networked and Distributed Systems (FORTE ‘03), Lecture Notes in Computer Science, Vol. 2767 (2003), Springer: Springer Berlin), 367-382 · Zbl 1279.68135
[4] J. Drissi, G.v. Bochmann, Submodule construction for systems of I/O automata, Technical Report #1133, DIRO, Université de Montréal, Canada, 1999.; J. Drissi, G.v. Bochmann, Submodule construction for systems of I/O automata, Technical Report #1133, DIRO, Université de Montréal, Canada, 1999.
[5] El-Fakih, K.; Yevtushenko, N., Fault propagation by equation solving, (Proc. IFIP 24th Internat. Conf. on Formal Techniques for Networked and Distributed Systems (FORTE ‘04), Lecture Notes in Computer Science, Vol. 3235 (2004), Springer: Springer Berlin), 185-198 · Zbl 1110.68350
[6] Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701
[7] Kelekar, S. G.H., Synthesis of protocols and protocol converters using the submodule construction approach, (Danthine, A.; etal., Protocol Specification, Testing, and Verification—PSTV XIII (1994))
[8] Kumar, R.; Nelvagal, S.; Marcus, S. I., A discrete event systems approach for protocol conversion, Discrete Event Dynamical Systems: Theory Appl., 7, 3, 295-315 (1997) · Zbl 0960.93034
[9] Merlin, P.; Bochman, G.v., On the construction of submodule specifications and communication protocols, ACM Trans. Programming Lang. Systems, 5, 1, 1-25 (1983) · Zbl 0498.68009
[10] Parrow, J., Submodule construction as equation solving in CCS, Theoret. Comput. Sci., 68 (1989) · Zbl 0686.68017
[11] Petrenko, A.; Yevtushenko, N., Solving asynchronous equations, (Bukowski, S.; Cavalli, A.; Najm, E., Formal Description Techniques and Protocol Specification, Testing, and Verification—FORTE XI/PSTVXVIII ‘98 (1998), Chapman & Hall: Chapman & Hall London), 231-247
[12] Petrenko, A.; Yevtushenko, N.; Bochmann, G.v.; Dssouli, R., Testing in context: framework and test derivation, Comput. Comm. J. Special issue on Protocol Eng., 19, 1236-1249 (1996)
[13] Qin, H.; Lewis, P., Factorisation of finite state machines under strong and observational equivalences, J. Formal Aspects Comput., 3, 284-307 (1991) · Zbl 0738.68029
[14] Tao, Z.; Bochmann, G.v.; Dssouli, R., A formal method for synthesizing optimized protocol converters and its application to mobile data networks, Mobile Networks Appl., 2, 3, 259-269 (1997)
[15] Wonham, W. M.; Ramadge, P. J., On the supremal controllable sublanguage of a given language, SIAM J. Control Optim., 25, 3, 637-659 (1987)
[16] Yevtushenko, N.; Villa, T.; Brayton, R. K.; Petrenko, A.; Sangiovanni-Vincentelli, A., Solution of parallel language equations for logic synthesis, (Proc. Internat. Conf. on Computer-Aided Design (2001)), 103-110
[17] N. Yevtushenko, T. Villa, A. Petrenko, R.K. Brayton, A. Sangiovanni-Vincentelli, Logic synthesis by equation solving, Technical Report, Tomsk State University, Russia, 1999, p. 27 (in Russian).; N. Yevtushenko, T. Villa, A. Petrenko, R.K. Brayton, A. Sangiovanni-Vincentelli, Logic synthesis by equation solving, Technical Report, Tomsk State University, Russia, 1999, p. 27 (in Russian).
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.