On Weighted Petri Net Transducers

详细信息    查看全文

• 作者：Robert Lorenz (17)
  Markus Huber (17)
  Günther Wirsching (18)
  
• 关键词：Petri Net ; Petri Net Transducer ; Weighted Transducer ; Labelled Partial Order ; Weighted Labelled Partial Order ; Partial Language ; Semiring ; Bisemiring ; Concurrent Semiring ; Cleanness
• 刊名：Lecture Notes in Computer Science
• 出版年：2014
• 出版时间：2014
• 年：2014
• 卷：8489
• 期：1
• 页码：233-252
• 全文大小：354 KB
• 参考文献：1. Azéma, P., Balbo, G. (eds.): ICATPN 1997. LNCS, vol.?1248. Springer, Heidelberg (1997)
  2. Best, E., Devillers, R.R., Hall, J.G.: The box calculus: a new causal algebra with multi-label communication. In: Rozenberg [19], pp. 21-9
  3. Boudol, G., Castellani, I.: On the semantics of concurrency: Partial orders and transition systems. In: Ehrig, H., Levi, G., Montanari, U. (eds.) CAAP 1987 and TAPSOFT 1987. LNCS, vol.?249, pp. 123-37. Springer, Heidelberg (1987)
  4. Chothia, T., Klejin, J.: Q-automata: Modelling the resource usage of concurrent components. Electronic Notes in Theoretical Computer Science?175(175), 153-67 (2007) CrossRef
  5. Droste, M., Kuich, W.: Semirings and Formal Power Series. In: Droste, et al. (eds.) [6], ch.1, pp. 3-8 (2009)
  6. Droste, M., Kuich, W., Vogler, H. (eds.): Handbook of Weighted Automata. Monographs in Theoretical Computer Science. Springer (2009)
  7. Esposito, A., Esposito, A.M., Vinciarelli, A., Hoffmann, R., Müller, V.C. (eds.): COST 2102. LNCS, vol.?7403. Springer, Heidelberg (2012)
  8. Fichtner, I., Kuske, D., Meinecke, I.: Traces, Series-Parallel Posets, and Pictures: A Weighted Study. In: Droste, et al. (eds.) [6], ch. 10, pp. 405-52 (2009)
  9. Füll?p, Z., Vogler, H.: Weighted Tree Automata and Tree Transducers. In: Droste, et al. (eds.) [6], ch. 9, pp. 313-04 (2009)
  10. Gischer, J.L.: The equational theory of pomsets. Theoretical Computer Science?61, 199-24 (1988) CrossRef
  11. Grabowski, J.: On Partial Languages. Fundamenta Informaticae?4(2), 428-98 (1981)
  12. Hack, M.: Petri net languages. Technical Report Memo 124, computation structures group, massachusetts institute of technology (1975)
  13. Hoare, T., M?ller, B., Struth, G., Wehrman, I.: Concurrent Kleene algebra and its foundations. The Journal of Logic and Algebraic Programming?80, 266-96 (2011) CrossRef
  14. Kuske, D., Meinecke, I.: Branching automata with costs - a way of reflecting parallelism in costs. Theoretical Computer Science?328, 53-5 (2004) CrossRef
  15. Lorenz, R., Huber, M.: Petri net transducers in semantic dialogue modelling. In: Proceedings of “Elektronische Sprachsignalverarbeitung (ESSV)- Studientexte zur Sprachkommunikation, vol.?64, pp. 286-97 (2012)
  16. Lorenz, R., Huber, M.: Realizing the Translation of Utterances into Meanings by Petri Net Transducers. In: Proceedings of “Elektronische Sprachsignalverarbeitung (ESSV)- Studientexte zur Sprachkommunikation, vol.?65 (2013)
  17. Mohri, M.: Weighted Automata Algorithms. In: Droste, et al. (eds.) [6], ch. 6, pp. 213-54 (2009)
  18. Pratt, V.: Modelling Concurrency with Partial Orders. Int. Journal of Parallel Programming?15, 33-1 (1986) CrossRef
  19. Rozenberg, G. (ed.): Advances in Petri Nets 1992, The DEMON Project. Springer (1992)
  20. Stra?ner, D.: Prototypische Implementierung von Petrinetz-Transduktoren mit SNAKES. Bachelor thesis, Augsburg University (2013)
  21. van Biljon, W.R.: Extending Petri nets for specifying man-machine dialogues. Int. J. Man-Mach. Stud.?28(4), 437-55 (1988) CrossRef
  22. van der Aalst, W.M.P.: Verification of workflow nets. In: Azéa, Balbo (eds.) [1], pp. 407-26
  23. Wang, F.-Y., Mittmann, M., Saridis, G.N.: Coordination specification for CIRSSE robotic platform system using Petri net transducers. Journal of Intelligent and Robotic Systems?9, 209-33 (1994) CrossRef
  24. Wang, F.-Y., Saridis, G.N.: A model for coordination of intelligent machines using Petri nets. In: Proceedings of the IEEE International Symposium on Intelligent Control, pp. 28-3. IEEE Comput. Soc. Press (1989)
  25. Wirsching, G., Huber, M., K?lbl, C.: Zur Logik von Bestenlisten in der Dialogmodellierung. In: Proceedings of “Elektronische Sprachsignalverarbeitung (ESSV)- Studientexte zur Sprachkommunikation, vol.?61, pp. 309-16 (2011)
  26. Wirsching, G., Huber, M., K?lbl, C., Lorenz, R., R?mer, R.: Semantic dialogue modeling. In: Esposito, et al. (eds.) [7], pp. 104-13
  27. Wolff, M.: Akustische Mustererkennung. Habilitation (2009)
  
• 作者单位：Robert Lorenz (17)
  Markus Huber (17)
  Günther Wirsching (18)
  
  17. Department of Computer Science, University of Augsburg, Germany
  18. Mathematisch-Geographische Fakult?t, Catholic University of Eichst?tt, Germany
  
• ISSN：1611-3349

文摘

In this paper we present a basic framework for weighted Petri net transducers (PNTs) for the translation of partial languages (consisting of partial words) as a natural generalisation of finite state transducers (FSTs). Concerning weights, we use the algebraic structure of continuous concurrent semirings which is based on bisemirings and induces a natural order on its elements. Using the operations of this algebra, it is possible to define the weight of sequential parallel partial words in a standard way. We define the weight of a general partial word as the supremum of the weights of all of its sequential parallel extensions. As a fundamental result we show that concurrent semirings are the least restrictive idempotent bisemiring structure such that partial words with fewer dependencies have bigger weights. Moreover, the weight definition turns out to be compositional, i.e. the weight of (sequential or parallel) composed partial words equals the corresponding bisemiring composition of the weights of its components. To be able to create complex PNTs through composition of simple PNTs, we introduce clean PNTs and the composition operations union, product, closure, parallel product and language composition on clean PNTs, lifting standard composition operations on FSTs. Composed PNTs yield a compositional computation of weights, where in the case of language composition such a compositional computation is possible only in restricted cases. Moreover, we give definitions for equivalent PNTs and show that all composition operations preserve equivalence. We also show that under certain conditions concerning the algebraic weight structure an FST can be represented by an equivalent PNT.