Petri Net Controlled Finite Automata

• Autorzy: Farwer B. , Jantzen M. , Kudlek M. , Rölke H. , Zetzsche G.
• Języki publikacji: EN

Abstrakty

EN

We present a generalization of finite automata using Petri nets as control, called Concurrent Finite Automata for short. Several modes of acceptance, defined by final markings of the Petri net, are introduced, and their equivalence is shown. The class of languages obtained by l-free concurrent finite automata contains both the class of regular sets and the class of Petri net languages defined by final marking, and is contained in the class of context-sensitive languages.

Słowa kluczowe

EN

finite automata; Petri net

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 85, nr 1-4
• Strony: 111--121
• Opis fizyczny: bibliogr. 8 poz., wykr.

Twórcy

autor

Farwer B.

autor

Jantzen M.

autor

Kudlek M.

autor

Rölke H.

autor

Zetzsche G.

• Universität Hamburg Fachbereich Informatik Vogt-Kölln-Str. 30 D-22527 Hamburg, Germany,

Bibliografia

• [1] B. Farwer, M. Kudlek, H. R¨olke: Petri-Net-Controlled Machine Models. FBI-Bericht 274, Hamburg, 2006.
• [2] B. Farwer, M. Kudlek, H. R¨olke: Concurrent Turing Machines as Rewrite Theories. In Proc. Concurrency, Specification and Programming. eds. G. Lindemann, H. Schlingloff, H.-D. Burkhard, L. Czaja, W. Penczek, A. Salwicki, A. Skowron, Z. Suraj, Vol. 3: Programming, pp. 352-363, 2006.
• [3] S. Greibach: Remarks on Blind and partially Blind Multicounter Machines. TCS 7, pp.311-324, 1978.
• [4] M. Hack: Petri Net Languages.MIT, Project MAC, Computation Structures Group Memo 124, 1975.
• [5] M. Jantzen: On the Hierarchy of Petri Net Languages. RAIRO 13, no. 1, pp. 19-30, 1979.
• [6] M. Jantzen: SynchronizationOperations and Formal Languages. In : Fifth Conference of Program Designers. ed. A. Iv´anyi, E¨otv¨os Lor´and University, Faculty of Natural Sciences, Budapest, pp. 15-26, 1989.
• [7] M. Mukund: Petri Nets and Step Transition Systems. IJFCS 3, no. 4, pp. 443-478, 1992.
• [8] J. L. Peterson: Computation Sequence Sets. JCSS 13, pp. 1-24, 1976.