Asynchronous cellular automata for pomsets
without auto-concurrency

P. GASTIN

IBP-Litp 1996/25: Rapport de Recherche Litp / Litp research reports
17 pages - Juillet/July 1996 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Asynchronous cellular automata for pomsets
without auto-concurrency

Résumé : Résumé : Ce papier généralise aux pomsets sans auto-concurrence la notion fondamentale d'automates asynchrones cellulaires (ACA) introduite originellement par Zielonka pour les traces. On généralise aussi la notion d'application asynchrone et on montre comment construire un ACA déterministe à partir d'une application asynchrone. Notre résultat principal est une généralisation du théorème de Büchi à une classe de pomsets sans auto-concurrence qui satisfait un axiome naturel. Cet axiome assure que l'automate asynchrone cellulaire fonctionne sur les pomsets comme une machine à lectures concurrentes et à écritures exclusives et propriétaires (CREOW). Plus précisément, on prouve l'équivalence pour cette classe de pomsets entre les ACA non déterministes, les ACA déterministes et la logique monadique du second ordre.

Abstract : Abstract : This paper extends to pomsets without auto-concurrency the fundamental notion of asynchronous cellular automata (ACA) which was originally introduced for traces by Zielonka. We generalize to pomsets the notion of asynchronous mapping introduced by Zielonka and we show how to construct a deterministic ACA from an asynchronous mapping. Our main result generalizes Büchi's theorem for a class of pomsets without auto-concurrency which satisfy a natural axiom. This axiom ensures that an asynchronous cellular automaton works on the pomset as a concurrent read owner write machine. More precisely, we prove the equivalence between non deterministic ACA, deterministic ACA and monadic second order logic for this class of pomsets.

Publications internes Litp 1996 / Litp research reports 1996