Title: On the complementation of Büchi asynchronous cellular automata
Abstract: We present a subset automaton construction for asynchronous cellular automata. This provides an answer to the problem of direct determinization for asynchronous cellular automata for finite traces, which has been open for several years. We use the subset automaton construction in order to extend Klarlund's progress measure technique of complementation to non-deterministic asynchronous cellular Büchi automata for infinite traces. Our automaton for the complement (as well as the subset automaton) has $$2^{O(N^{\left| \Sigma \right|} )} $$ global states.
Publication Year: 1994
Publication Date: 1994-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 16
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot