A complex measure for linear grammars

• Autorzy: Chattopadhyay I. , Ray A.
• Języki publikacji: EN

Abstrakty

EN

The signed real measure of regular languages, introduced and validated in recent literature, has been the driving force for quantitative analysis and synthesis of discrete-event supervisory (DES) control systems dealing with finite state automata (equivalently, regular languages). However, this approach relies on memoryless state-based tools for supervisory control synthesis and may become inadequate if the transitions in the plant dynamics cannot be captured by finitely many states. From this perspective, the measure of regular languages needs to be extended to that of non-regular languages, such as Petri nets or other higher level languages in the Chomsky hierarchy. Measures for non-regular languages has not apparently been reported in open literature and is an open area of research. As a step toward achieving this goal, this paper introduces a complex measure of linear context free grammars (LCFG) that belong to the class of non-regular languages. The proposed complex measure becomes equivalent to the signed real measure, reported in recent literature, if the LCFG is degenerated to a regular grammar.

Słowa kluczowe

EN

linear grammars; nonregular languages; quantitative analysis; discrete event supervisory control

• Wydawca: De Gruyter
• Czasopismo: Demonstratio Mathematica
• Rocznik: 2005
• Tom: Vol. 38, nr 3
• Strony: 761--775
• Opis fizyczny: Bibliogr. 8 poz.

Twórcy

autor

Chattopadhyay I.

• The Pennsylvania State University, University Park, PA 16802, USA

autor

Ray A.

• The Pennsylvania State University, University Park, PA 16802, USA

Bibliografia

• [1] I. Chattopadhyay, A. Ray, and X. Wang, A Complex Measure of Non-Regular Languages for Discrete-Event Supervisory Control, Proceedings of American Control Conference, Boston, MA (2004), pp. 5120-5125.
• [2] J. E. Hopcroft, R. Motwani, and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, 2nd ed., Addison-Wesley, 2001.
• [3] J. O. Moody and P. J. Antsaklis, Supervisory Control of Discrete Event Systems Using Petri Nets, Kluwer Academic, 1998.
• [4] P. J. Ramadge and W. M. Wonham, Supervisory control of a class of discrete event processes, SIAM J. Control Optim. 25 (1987), no. 1, 206-230.
• [5] A. Ray, J. Fu, and C. Lagoa, Optimal supervisory control of finite state automata, Internat. J. Control 77 (2004), no. 12, 1083-1100.
• [6] W. Rudin, Real and Complex Analysis, 3rd ed., McGraw Hill, New York, 1988.
• [7] A. Surana and A. Ray, Measure of regular languages, Demonstratio Math. 37 (2004), no. 2, 485-503.
• [8] X. Wang, A. Ray and A. Khatkhate, On-line Identification of Language Measure Parameters for Discrete Event Supervisory Control, Applied Mathematical Modelling29 (2005), no. 6, 597-613.