On the Expressiveness of Asynchronous Cellular Automata

1. Abdulla, P.A., Jonsson, B.: Verifying programs with unreliable channels. In: Proceedings of LICS 1993. IEEE Computer Society Press, Los Alamitos (1993)

   Google Scholar 

2. Bollig, B., Leucker, M.: Message-Passing Automata are expressively equivalent to EMSO Logic. In: Gardner, P., Yoshida, N. (eds.) CONCUR 2004. LNCS, vol. 3170, pp. 146–160. Springer, Heidelberg (2004)

   Chapter  Google Scholar 

3. Brand, D., Zafiropulo, P.: On communicating finite-state machines. Journal of the ACM 30(2) (1983)

   Google Scholar 

4. Cécé, G., Finkel, A., Purushothaman Iyer, S.: Unreliable channels are easier to verify than perfect channels. Information and Computation 124(1) (1996)

   Google Scholar 

5. Diekert, V., Rozenberg, G. (eds.): The Book of Traces. World Scientific, Singapore (1995)

   Google Scholar 

6. Droste, M., Gastin, P., Kuske, D.: Asynchronous cellular automata for pomsets. Theoretical Computer Science 247(1-2) (2000)

   Google Scholar 

7. Finkel, A.: Decidability of the termination problem for completely specified protocols. Distributed Computing 7(3) (1994)

   Google Scholar 

8. Genest, B., Muscholl, A., Kuske, D.: A Kleene theorem for a class of communicating automata with effective algorithms. In: Calude, C.S., Calude, E., Dinneen, M.J. (eds.) DLT 2004. LNCS, vol. 3340, pp. 30–48. Springer, Heidelberg (2004)

   Google Scholar 

9. Hanf, W.P.: Model-theoretic methods in the study of elementary logic. In: The Theory of Models. North-Holland, Amsterdam (1965)

   Google Scholar 

10. Henriksen, J.G., Mukund, M., Narayan Kumar, K., Thiagarajan, P.S.: Regular collections of message sequence charts. In: Nielsen, M., Rovan, B. (eds.) MFCS 2000. LNCS, vol. 1893, p. 405. Springer, Heidelberg (2000)

    Google Scholar 

11. Kuske, D.: Emptiness is decidable for asynchronous cellular machines. In: Palamidessi, C. (ed.) CONCUR 2000. LNCS, vol. 1877, p. 536. Springer, Heidelberg (2000)

    Google Scholar 

12. Matz, O., Schweikardt, N., Thomas, W.: The monadic quantifier alternation hierarchy over grids and graphs. Information and Computation 179(2) (2002)

    Google Scholar 

13. Potthoff, A., Seibert, S., Thomas, W.: Nondeterminism versus determinism of finite automata over directed acyclic graphs. Bulletin of the Belgian Mathematical Society 1 (1994)

    Google Scholar 

14. Thomas, W.: On Logics, Tilings, and Automata. In: Leach Albert, J., Monien, B., Rodríguez-Artalejo, M. (eds.) ICALP 1991. LNCS, vol. 510. Springer, Heidelberg (1991)

    Google Scholar 

15. Thomas, W.: Elements of an automata theory over partial orders. In: Proceedings of POMIV 1996. DIMACS, vol. 29, AMS (1996)

    Google Scholar 

16. Thomas, W.: Automata theory on trees and partial orders. In: Bidoit, M., Dauchet, M. (eds.) CAAP 1997, FASE 1997, and TAPSOFT 1997. LNCS, vol. 1214. Springer, Heidelberg (1997)

    Chapter  Google Scholar 

17. Wiesław Zielonka. Notes on finite asynchronous automata. R.A.I.R.O. — Informatique Théorique et Applications, 21 (1987)

    Google Scholar 

Download references