Traces, Series-Parallel Posets, and Pictures: A Weighted Study
作者： Ina Fichtner , Dietrich Kuske , Ingmar Meinecke
DOI: 10.1007/978-3-642-01492-5_10
关键词: Automata theory 、 Mathematics 、 Nested word 、 Cellular automaton 、 Concurrency 、 Partially ordered set 、 Discrete mathematics 、 Theoretical computer science 、 Quantum finite automata 、 ω-automaton 、 Finite-state machine
摘要: Words and finite automata over words are central notions in computer science. They model the sequential executions of systems. However, both world its own science have to cope with another phenomenon as well: concurrency. Then not all events be ordered but some actions may appear independently. On other hand, can seen one-dimensional objects, higher-dimensional objects like two-dimensional rectangles or pictures handled well. This chapter is concerned weighted that describe quantitative aspects partially sets pictures. More specifically, we first consider asynchronous cellular compute semiring valuations Mazurkiewicz traces. In a similar spirit, branching associate weights series-parallel pomsets. Thirdly, picture arrays colors. We characterize expressive power these by rational expressions monadic second-order logics.
springer.com
harvard.edu
sci-hub.st 参考文章(65)
Ingmar Meinecke, The Hadamard Product of Sequential-Parallel Series. Journal of Automata, Languages and Combinatorics. ,vol. 10, pp. 313- 346 ,(2005)
A. Arnold, An extension of the notions of traces and of asynchronous automata Theoretical Informatics and Applications. ,vol. 25, pp. 355- 393 ,(1991) , 10.1051/ITA/1991250403551
Jan Grabowski, On Partial Languages Fundamenta Informaticae. ,vol. 4, pp. 427- 498 ,(1981) , 10.3233/FI-1981-4210
Wieslaw Zielonka, Notes on finite asynchronous automata RAIRO - Theoretical Informatics and Applications. ,vol. 21, pp. 99- 135 ,(1987) , 10.1051/ITA/1987210200991
Symeon Bozapalidis, Archontia Grammatikopoulou, Recognizable Picture Series. Journal of Automata, Languages and Combinatorics. ,vol. 10, pp. 159- 183 ,(2005)
Edward Ochmanski, Regular behaviour of concurrent systems. Bulletin of The European Association for Theoretical Computer Science. ,vol. 27, pp. 56- 67 ,(1985)
Dietrich Kuske, Weighted and unweighted trace automata Acta Cybernetica. ,vol. 19, pp. 393- 410 ,(2009)
Stéphane Gaubert, Jean Mairesse, Idempotency: Task resource models and (max, +) automata ,(1998) , 10.1017/CBO9780511662508.009
Ina Mäurer, Weighted picture automata and weighted logics symposium on theoretical aspects of computer science. pp. 313- 324 ,(2006) , 10.1007/11672142_25
Dietrich Kuske, Rémi Morin, Pomsets for Local Trace Languages - Recognizability, Logic & Petri Nets international conference on concurrency theory. pp. 426- 441 ,(2000)