{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T15:54:36Z","timestamp":1784217276965,"version":"3.55.0"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2005,6,1]],"date-time":"2005-06-01T00:00:00Z","timestamp":1117584000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Event Dyn Syst"],"published-print":{"date-parts":[[2005,6]]},"DOI":"10.1007\/s10626-004-6210-5","type":"journal-article","created":{"date-parts":[[2005,2,18]],"date-time":"2005-02-18T13:22:11Z","timestamp":1108732931000},"page":"145-167","source":"Crossref","is-referenced-by-count":17,"title":["PSPACE-completeness of Modular Supervisory Control Problems*"],"prefix":"10.1007","volume":"15","author":[{"given":"Kurt","family":"Rohloff","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"St\ufffdphane","family":"Lafortune","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/BF01797138","volume":"6","author":"N. Ben Hadj-Alouane","year":"1996","unstructured":"Ben Hadj-Alouane, N., Lafortune, S., and Lin, F. 1996. Centralized and distributed algorithms for on-line synthesis of maximal control policies under partial observation. J. Discrete Event Dyn. Syst.: Theory Appl. 6: 379?427.","journal-title":"J. Discrete Event Dyn. Syst.: Theory Appl."},{"key":"CR2","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0304-3975(94)00132-3","volume":"139","author":"A. Bergeron","year":"1995","unstructured":"Bergeron, A. 1995. Sharing out control in distributed processes. Theor. Comp. Sci. 139: 163?186.","journal-title":"Theor. Comp. Sci."},{"issue":"9","key":"CR3","doi-asserted-by":"crossref","first-page":"1249","DOI":"10.1016\/S0005-1098(00)00050-9","volume":"36","author":"V. D. Blondel","year":"2003","unstructured":"Blondel, V. D., and Tsitsiklis, J. N. 2003. A survey of computational complexity results in systems and control. Automatica 36(9): 1249?1274.","journal-title":"Automatica"},{"key":"CR4","unstructured":"Brandin, B. A., Malik, R., and Dietrich, P. 2000. Incremental system verification and synthesis of minimally restrictive behaviors. In Proc. of 2000 American Control Conference, pp. 4056?4061."},{"key":"CR5","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/S0304-3975(96)00178-8","volume":"189","author":"H.-D. Burkhard","year":"1997","unstructured":"Burkhard, H. -D. 1997. Fairness and control in multi-agent systems. Theor. Comp. Sci. 189: 109?127.","journal-title":"Theor. Comp. Sci."},{"key":"CR6","first-page":"525","volume":"5","author":"S. Buss","year":"1991","unstructured":"Buss, S., Papadimitriou, C., and Tsitsiklis, J. 1991. On the predictability of coupled automata: An allegory about chaos. Complex Syst. 5: 525?539.","journal-title":"Complex Syst."},{"key":"CR7","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-4070-7","volume-title":"Introduction to Discrete Event Systems","author":"C. G. Cassandras","year":"1999","unstructured":"Cassandras, C. G., and Lafortune, S. 1999. Introduction to Discrete Event Systems. Boston MA: Kluwer Academic Publishers."},{"issue":"3","key":"CR8","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1109\/9.402","volume":"33","author":"R. Cieslak","year":"1988","unstructured":"Cieslak, R., Desclaux, C., Fawaz, A., and Varaiya, P. 1988. Supervisory control of discrete-event processes with partial observations. IEEE Trans. Automat. Contr. 33(3): 249?260, March.","journal-title":"IEEE Trans. Automat. Contr."},{"key":"CR9","volume-title":"Theory of Computational Complexity","author":"D. Z. Du","year":"2000"},{"key":"CR10","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"Garey, M. R., and Johnson, D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman."},{"issue":"5","key":"CR11","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1109\/3477.875441","volume":"30","author":"P. Gohari","year":"2000","unstructured":"Gohari, P., and Wonham, W. M. 2000. On the complexity of supervisory control design in the RW framework. IEEE Trans. Syst. Man Cybern., Part B 30(5): 643?652.","journal-title":"IEEE Trans. Syst. Man Cybern., Part B"},{"key":"CR12","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1006\/inco.2001.2920","volume":"173","author":"D. Harel","year":"2002","unstructured":"Harel, D., Kupferman, O., and Vardi, M. Y. 2002. On the complexity of verifying concurrent transition systems. Inf. Comput. 173: 143?161.","journal-title":"Inf. Comput."},{"key":"CR13","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1016\/S0304-3975(99)00038-9","volume":"221","author":"T. A. Henzinger","year":"1999","unstructured":"Henzinger, T. A., and Kopke, P. W. 1999. Discrete-time control for rectangular hybrid automata. Theor. Comp. Sci. 221: 369?392.","journal-title":"Theor. Comput. Sci."},{"key":"CR14","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J. Hopcroft","year":"1979","unstructured":"Hopcroft, J., and Ullman, J. 1979. Introduction to Automata Theory, Languages, and Computation. Reading, MA, USA: Addison Wesley."},{"issue":"5","key":"CR15","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1109\/3477.875442","volume":"30","author":"S. Jiang","year":"2000","unstructured":"Jiang, S., and Kumar, R. 2000. Decentralized control of discrete event systems with specialization to local control and concurrent systems. IEEE Trans. Syst. Man Cybern., Part B 30(5): 653?660.","journal-title":"IEEE Trans. Syst. Man Cybern., Part B"},{"key":"CR16","unstructured":"Jiang, S., Chandra, V., and Kumar R. 2001. Decentralized control of discrete event systems with multiple local specializations. In Proc. of 2001 American Control Conference, pp. 959?964."},{"key":"CR17","doi-asserted-by":"crossref","unstructured":"Kozen, D. 1977. Lower bounds for natural proof systems. In Proc. 18th Symp. on the Foundations of Computer Science, pp. 254?266.","DOI":"10.1109\/SFCS.1977.16"},{"issue":"2","key":"CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4086\/cjtcs.1998.002","volume":"1998","author":"O. Kupferman","year":"1998","unstructured":"Kupferman, O., and Vardi, M. 1998. Verification of fair transition systems. Chic. J. Theor. Comput. Sci. 1998(2): 1?37.","journal-title":"Chic. J. Theor. Comput. Sci."},{"key":"CR19","unstructured":"Kupferman, O., and Vardi, M. 2001. Synthesizing distributed systems. In Proc. 16th IEEE Symp on Logic Computer Science, pp. 81?92."},{"issue":"2","key":"CR20","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1145\/333979.333987","volume":"47","author":"O. Kupferman","year":"2000","unstructured":"Kupferman, O., Vardi, M., and Wolper, P. 2000. An automata-theoretic approach to branching-time model checking. J. ACM 47(2): 312?360.","journal-title":"J. ACM"},{"key":"CR21","doi-asserted-by":"crossref","unstructured":"Lange, K.-J., and Rossmanith, P. 1992. The emptiness problem for intersections of regular languages. In I. Havel (ed.), Proc. of the 17th Conf. on Mathematical Foundations of Computer Science, number 629 in LNCS, Springer-Verlag, pp. 346?354.","DOI":"10.1007\/3-540-55808-X_33"},{"key":"CR22","doi-asserted-by":"crossref","unstructured":"Leduc, R. J., Brandin, B., Lawford, M., and Wonham, W. M. 2001a. Hierarchical interface-based supervisory control: Serial case. In Proc. 40th IEEE Conf. on Decision and Control, pp. 4116?4121.","DOI":"10.1109\/CDC.2001.980825"},{"key":"CR23","unstructured":"Leduc, R. J., Lawford, M., and Wonham, W. M. 2001b. Hierachical interface-based supervisory control: AIP example. In 39th Allerton Conf. on Comm., Contr., and Comp."},{"key":"CR24","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0020-0255(88)90002-3","volume":"44","author":"F. Lin","year":"1988","unstructured":"Lin, F., and Wonham, W. M. 1988a. Decentralized supervisory control of discrete-event systems. Inf. Sci. 44: 199?224.","journal-title":"Inf. Sci."},{"key":"CR25","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/0020-0255(88)90001-1","volume":"44","author":"F. Lin","year":"1988","unstructured":"Lin, F., and Wonham, W. M. 1988b. On observability of discrete-event systems. Inf. Sci. 44: 173?198.","journal-title":"Inf. Sci."},{"key":"CR26","doi-asserted-by":"crossref","unstructured":"Madhusudan, P., and Thiagarajan, P. S. 2001. Distributed controller synthesis for local specifications. In Proc. 28th Int. Colloquium Automata, Languages and Programming, pp. 396?407.","DOI":"10.1007\/3-540-48224-5_33"},{"key":"CR27","doi-asserted-by":"crossref","unstructured":"Pnueli, A., and Rosner, R. 1990. Distributed reactive systems are hard to synthesize. In Proc. 31st Symp on the Foundations of Computer Science, pp. 746?757","DOI":"10.1109\/FSCS.1990.89597"},{"key":"CR28","doi-asserted-by":"crossref","unstructured":"Queiroz, M. H., and Cury, J. E. R. 2000. Modular control of composed systems. In Proc. of 2000 American Control Conference.","DOI":"10.1109\/ACC.2000.876983"},{"issue":"1","key":"CR29","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1109\/9.8645","volume":"34","author":"J. Ramadge","year":"1989","unstructured":"Ramadge, P. J. 1989. Some tractable supervisory control problems for discrete-event systems modeled by Buchi automata. IEEE Trans. Automat. Contr. 34(1): 10?19","journal-title":"IEEE Trans. Automat. Contr."},{"issue":"1","key":"CR30","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1137\/0325013","volume":"25","author":"P. J. Ramadge","year":"1987","unstructured":"Ramadge, P. J., and Wonham, W. M. 1987. Supervisory control of a dass of discrete-event processes. SIAM J. Control Optim. 25(1): 206?230.","journal-title":"SIAM J. Control Optim."},{"issue":"1","key":"CR31","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1109\/5.21072","volume":"77","author":"P. J. Ramadge","year":"1989","unstructured":"Ramadge, P. J., and Wonhamm, W. M. 1989. The control of discrete-event systems. Proc. IEEE 77(1): 81?98.","journal-title":"Proc. IEEE"},{"issue":"9","key":"CR32","doi-asserted-by":"crossref","first-page":"1656","DOI":"10.1109\/9.880616","volume":"45","author":"S. L. Ricker","year":"2000","unstructured":"Ricker, S. L., and Rudie, K. 2000. Incorporating knowledge into discrete-event control systems. IEEE Trans. Automat. Contr. 45(9): 1656?1668.","journal-title":"IEEE Trans. Automat. Contr."},{"issue":"6","key":"CR33","doi-asserted-by":"crossref","first-page":"1064","DOI":"10.1109\/TAC.2003.812812","volume":"48","author":"K. Rohloff","year":"2003","unstructured":"Rohloff, K., and Lafortune, S. 2003. On the synthesis of safe control policies in decentralized control of discrete event systems. IEEE Trans. Automat. Contr. 48(6): 1064?1068.","journal-title":"IEEE Trans. Automat. Contr."},{"issue":"11","key":"CR34","doi-asserted-by":"crossref","first-page":"1995","DOI":"10.1109\/TAC.2003.819285","volume":"48","author":"K. Rohloff","year":"2003","unstructured":"Rohloff, K., Yoo, T.-S., and Lafortune, S. 2003. Deciding co-observability is PSPACE-complete. IEEE Trans. Automat. Contr. 48(11): 1995?1999.","journal-title":"IEEE Trans. Automat. Contr."},{"issue":"7","key":"CR35","doi-asserted-by":"crossref","first-page":"1313","DOI":"10.1109\/9.400469","volume":"40","author":"K. Rudie","year":"1995","unstructured":"Rudie, K., and Willems, J. C. 1995. The computational complexity of decentralized discrete-event control problems. IEEE Trans. Automat. Contr. 40(7): 1313?1318.","journal-title":"IEEE Trans. Automat. Contr."},{"issue":"11","key":"CR36","doi-asserted-by":"crossref","first-page":"1692","DOI":"10.1109\/9.173140","volume":"37","author":"K. Rudie","year":"1992","unstructured":"Rudie, K., and Wonham, W. M. 1992. Think globally, act locally: Decentralized supervisory control. IEEE Trans. Automat. Contr. 37(11): 1692?1708, November.","journal-title":"IEEE Trans. Automat. Contr."},{"issue":"2","key":"CR37","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W. J. Savitch","year":"1970","unstructured":"Savitch, W. J. 1970. Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci. 4(2): 177?192.","journal-title":"J. Comput. Syst. Sci."},{"key":"CR38","doi-asserted-by":"crossref","unstructured":"Takai, S., and Ushio, T. 2000. On-line decentralized supervisory control of discrete event systems. In Proc. 39th IEEE Conf. Decis. Control, December, pp. 7?8.","DOI":"10.1109\/CDC.2000.912723"},{"key":"CR39","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/inco.1994.1092","volume":"115","author":"M. Vardi","year":"1994","unstructured":"Vardi, M., and Wolper, P. 1994. Reasoning about infinite computations. Inf. Comput. 115: 1?37.","journal-title":"Inf. Comput."},{"issue":"5","key":"CR40","doi-asserted-by":"crossref","first-page":"1143","DOI":"10.1080\/00207179108934202","volume":"54","author":"Y. Willner","year":"1991","unstructured":"Willner, Y., and Heyman, M. 1991. Supervisory control of concurrent discrete event systems. Int. J. Control 54(5): 1143?1169.","journal-title":"Int. J. Control"},{"key":"CR41","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1023\/A:1008210519960","volume":"8","author":"K. C. Wong","year":"1998","unstructured":"Wong, K. C., and Wonham, W. M. 1998. Modular control and coordination of discrete-event systems. J. Discret. Event Dyn. Syst.: Theory Appl. 8: 247?297.","journal-title":"J. Discret. Event Dyn. Syst.: Theory Appl."},{"issue":"1","key":"CR42","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF02551233","volume":"1","author":"W. M. Wonham","year":"1988","unstructured":"Wonham, W. M., and Ramadge, P. J. 1988. Modular supervisory control of discrete event systems. Math. Control Signals Syst. 1(1): 13?30.","journal-title":"Math. Control Signals Syst."},{"issue":"3","key":"CR43","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1023\/A:1015625600613","volume":"13","author":"T.-S. Yoo","year":"2002","unstructured":"Yoo, T.-S., and Lafortune, S. 2002. A general architecture for decentralized supervisory control of discrete-event systems. J. Discret. Event Dyn. Syst.: Theory Appl. 13(3): 335?377.","journal-title":"J. Discret. Event Dyn. Syst.: Theory Appl."}],"container-title":["Discrete Event Dynamic Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10626-004-6210-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10626-004-6210-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10626-004-6210-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T15:58:49Z","timestamp":1559231929000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10626-004-6210-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,6]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,6]]}},"alternative-id":["6210"],"URL":"https:\/\/doi.org\/10.1007\/s10626-004-6210-5","relation":{},"ISSN":["0924-6703","1573-7594"],"issn-type":[{"value":"0924-6703","type":"print"},{"value":"1573-7594","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,6]]}}}