Abstract
We propose a new method for controlled system synthesis on non-deterministic automata, which includes the synthesis for deadlock- freeness, as well as invariant and reachability expressions. Our technique restricts the behavior of a Kripke-structure with labeled transitions, representing the uncontrolled system, such that it adheres to a given requirement specification in an expressive modal logic, while all non-invalidating behavior is retained. This induces maximal permissiveness in the context of supervisory control. Research presented in this paper allows a system model to be constrained according to a broad set of liveness, safety and fairness specifications of desired behavior, and embraces most concepts from Ramadge-Wonham supervisory control, including controllability and marker-state reachability. The synthesis construction is formally verified using the Coq proof assistant.
Supported by the EU FP7 Programme under grant agreement No. 295261 (MEALS).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aminof, B., Mogavero, F., Murano, A.: Synthesis of hierarchical systems. In: Arbab, F., Ölveczky, P.C. (eds.) FACS 2011. LNCS, vol. 7253, pp. 42–60. Springer, Heidelberg (2012)
Arnold, A., Vincent, I., Walukiewicz, I.: Games for synthesis of controllers with partial observation. Theoretical Computer Science 1(303), 7–34 (2003)
Arnold, A., Walukiewicz, I.: Nondeterministic controllers of nondeterministic processes. In: Logic and Automata, pp. 29–52. Amsterdam University Press (2008)
Baeten, J., van Beek, B., van Hulst, A., Markovski, J.: A process algebra for supervisory coordination. In: Process Algebra and Coordination. EPTCS, pp. 36–55 (2011)
Bull, R., Segerberg, K.: Basic modal logic. In: Handbook of Philosophical Logic, pp. 1–88. Springer (1994)
Cassandras, C., Lafortune, S.: Introduction to Discrete Event Systems. Springer (1999)
Cleaveland, R., Steffen, B.: A linear-time model checking algorithm for the alternation-free modal mu-calculus. Formal Methods in System Design 2, 121–147 (1993)
D’Ippolito, N., Braberman, V., Piterman, N., Uchitel, S.: Synthesis of live behaviour models. In: Foundations of Software Engineering, pp. 77–86. ACM Press (2010)
D’Ippolito, N., Braberman, V., Piterman, N., Uchitel, S.: Synthesizing nonanomalous event-based controllers for liveness goals. ACM Transactions on Software Engineering Methodology 22(1), 1–36 (2013)
Hennessy, M., Milner, R.: Algebraic laws for nondeterminism and concurrency. Journal of the ACM 32(1), 137–161 (1985)
Lustig, Y., Vardi, M.: Synthesis from recursive-components libraries. In: Games, Automata, Logics and Formal Verification. EPTCS, pp. 1–16 (2011)
Pnueli, A., Rosner, R.: On the synthesis of a reactive module. In: Principles of Programming Languages, pp. 179–190. ACM Press (1989)
Ramadge, P., Wonham, W.: Supervisory control of a class of discrete event processes. SIAM Journal on Control and Optimization 25(1), 206–230 (1987)
Sokolsky, O., Smolka, S.: Incremental model checking in the modal mu-calculus. In: Dill, D.L. (ed.) CAV 1994. LNCS, vol. 818, pp. 351–363. Springer, Heidelberg (1994)
van Glabbeek, R.: The linear time-branching time spectrum II. In: Best, E. (ed.) CONCUR 1993. LNCS, vol. 715, pp. 66–81. Springer, Heidelberg (1993)
van Hulst, A.: Coq v8.3 proofs (2014), http://seweb.se.wtb.tue.nl/~ahulst/sofsem/
van Hulst, A., Reniers, M., Fokkink, W.: Maximal synthesis for Hennessy-Milner logic. In: Application of Concurrency to System Design, pp. 1–10. IEEE (2013)
van Hulst, A., Reniers, M., Fokkink, W.: Maximal synthesis for Hennessy-Milner logic with the box-modality. In: Workshop on Discrete Event Systems, pp. 278–285. IEEE (2014)
van Hulst, A., Reniers, M., Fokkink, W.: Maximally permissive controlled system synthesis for modal logic (2014), preprint at http://arxiv.org/abs/1408.3317/
Ziller, R., Schneider, K.: Combining supervisory synthesis and model checking. ACM Transactions on Embedded Computing Systems 4(2), 331–362 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
van Hulst, A.C., Reniers, M.A., Fokkink, W.J. (2015). Maximally Permissive Controlled System Synthesis for Modal Logic. In: Italiano, G.F., Margaria-Steffen, T., Pokorný, J., Quisquater, JJ., Wattenhofer, R. (eds) SOFSEM 2015: Theory and Practice of Computer Science. SOFSEM 2015. Lecture Notes in Computer Science, vol 8939. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-46078-8_19
Download citation
DOI: https://doi.org/10.1007/978-3-662-46078-8_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-46077-1
Online ISBN: 978-3-662-46078-8
eBook Packages: Computer ScienceComputer Science (R0)