SpringerLink
Log in

Determinizing asynchronous automata

  • Conference paper
  • First Online:
Automata, Languages and Programming (ICALP 1994)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 820))

Included in the following conference series:

  • 137 Accesses

Abstract

An asynchronous automaton consists of a set of processes that cooperate in processing letters of the input. Each letter read prompts some of the processes to synchronize and decide on a joint move according to a non-deterministic transition relation.

Zielonka's theorem tells us that these automata can be determinized while retaining the synchronization structure. Unfortunately, this construction is indirect and yields a triple-exponential blow-up in size.

We present a direct determinization procedure for asynchronous automata which generalizes the classical subset construction for finite-state automata. Our construction is only double-exponential and thus is the first to essentially match the lower bound.

The author is supported by a fellowship from the Danish Research Council.

The author was partially supported by IFCPAR Project 502-1

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. R. Cori, Y. Metivier, W. Zielonka: Asynchronous map**s and asynchronous cellular automata, Inf. and Comput., 106 (1993) 159–202.

    Google Scholar 

  2. V. Diekert, A. Muscholl: Deterministic asynchronous automata for infinite traces, Proc. STACS '93, LNCS 665 (1993) 617–628.

    Google Scholar 

  3. P. Gastin, A. Petit: Asynchronous cellular automata for infinite traces, Proc. ICALP '92, LNCS 623 (1992) 583–594.

    Google Scholar 

  4. N. Klarlund, M. Mukund, M. Sohoni: Determinizing asynchronous automata, Report DAIMI-PB 460, Computer Science Department, Aarhus University, Aarhus, Denmark (1993).

    Google Scholar 

  5. A. Mazurkiewicz: Basic notions of trace theory, in: J.W. de Bakker, W.-P. de Roever, G. Rozenberg (eds.), Linear time, branching time and partial order in logics and models for concurrency, LNCS 354, (1989) 285–363.

    Google Scholar 

  6. M. Mukund, M. Sohoni: Gossi**, asynchronous automata and Zielonka's theorem, Report TCS-94-2, School of Mathematics, SPIC Science Foundation, Madras (1994). See also “Kee** track of the latest gossip: Bounded timestamps suffice”, Proc. FST&TCS '93, LNCS 761 (1993) 388–399.

    Google Scholar 

  7. A. Muscholl: On the complementation of Büchi asynchronous cellular automata, Proc. ICALP 1994.

    Google Scholar 

  8. W. Zielonka: Notes on finite asynchronous automata, R.A.I.R.O.—Inf. Théor. et Appl., 21 (1987) 99–135.

    Google Scholar 

  9. W. Zielonka: Safe executions of recognizable trace languages, in Logic at Botik, LNCS 363 (1989) 278–289.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. BRICS Center, Aarhus University, Ny Munkegade, DK 8000, Aarhus C, Denmark

    Nils Klarlund

  2. School of Mathematics, SPIC Science Foundation, 92 G N Chetty Rd, 600 017, Madras, India

    Madhavan Mukund & Milind Sohoni

Authors
  1. Nils Klarlund
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Madhavan Mukund
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Milind Sohoni
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Serge Abiteboul Eli Shamir

Rights and permissions

Reprints and permissions

Copyright information

© 1994 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Klarlund, N., Mukund, M., Sohoni, M. (1994). Determinizing asynchronous automata. In: Abiteboul, S., Shamir, E. (eds) Automata, Languages and Programming. ICALP 1994. Lecture Notes in Computer Science, vol 820. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-58201-0_63

Download citation

  • DOI: https://doi.org/10.1007/3-540-58201-0_63

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-58201-4

  • Online ISBN: 978-3-540-48566-7

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation