Notes on finite asynchronous automata

DOI10.1051/ita/1987210200991zbMath0623.68055OpenAlexW89538287MaRDI QIDQ3761703

Publication date: 1987

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/92285

zbMATH Keywords

regular language traces trace language free partially commutative monoid finite asynchronous automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items (99)

Realizability of concurrent recursive programs ⋮ Asynchronous automata versus asynchronous cellular automata ⋮ Distributed Asynchronous Games With Causal Memory are Undecidable ⋮ Two optimal parallel algorithms on the commutation class of a word ⋮ Verification and comparison of transition systems ⋮ Realizability of high-level message sequence charts: closing the gaps ⋮ Undecidability of partial order logics ⋮ Automated Synthesis of Distributed Controllers ⋮ On interactive knowledge with bounded communication ⋮ A Canonical Contraction for Safe Petri Nets ⋮ On the complementation of asynchronous cellular Büchi automata ⋮ An extension of the notions of traces and of asynchronous automata ⋮ Distributed Asynchronous Automata ⋮ Theory of traces ⋮ Classifying Recognizable Infinitary Trace Languages Using Word Automata ⋮ 2-asynchronous automata ⋮ On Distributed Monitoring and Synthesis ⋮ The synthesis problem for repeatedly communicating Petri games ⋮ Classifying recognizable infinitary trace languages using word automata ⋮ Communicating Finite-State Machines and Two-Variable Logic ⋮ Solving high-level Petri games ⋮ Subclasses of recognizable trace languages ⋮ Automata and Logics for Concurrent Systems: Five Models in Five Pages ⋮ Automata for epistemic temporal logic with synchronous communication ⋮ A product version of dynamic linear time temporal logic ⋮ High-level representation of benchmark families for Petri games ⋮ A quadratic construction for Zielonka automata with acyclic communication structure ⋮ A study on shuffle, stopwatches and independently evolving clocks ⋮ Controlling loosely cooperating processes ⋮ Solving parity games by a reduction to SAT ⋮ Asynchronous cellular automata for pomsets without auto-concurrency ⋮ A PO characterisation of reconfiguration ⋮ Unnamed Item ⋮ Probabilistic asynchronous automata ⋮ A survey on automata with translucent letters ⋮ Unnamed Item ⋮ Contracts for cross-organizational workflows as timed dynamic condition response graphs ⋮ Communicating finite-state machines, first-order logic, and star-free propositional dynamic logic ⋮ Distribution and synchronized automata ⋮ MSO Logic for Unambiguous Shared-Memory Systems ⋮ Modelling concurrency with comtraces and generalized comtraces ⋮ Asynchronous trace-matching automata ⋮ Semantics of Deterministic Shared-Memory Systems ⋮ Keeping track of the latest gossip in a distributed system ⋮ Temporal logics for concurrent recursive programs: satisfiability and model checking ⋮ Recognizable closures and submonoids of free partially commutative monoids ⋮ Determinizing asynchronous automata ⋮ On the complementation of Büchi asynchronous cellular automata ⋮ A kleene theorem for recognizable languages over concurrency monoids ⋮ Reordering Derivatives of Trace Closures of Regular Languages. ⋮ Event structures and trace monoids ⋮ Probabilistic estimation of the number of prefixes of a trace ⋮ Basic notions of universal algebra for language theory and graph grammars ⋮ Logical definability on infinite traces ⋮ Compilation of the ELECTRE reactive language into finite transition systems ⋮ Shared-Memory Systems and Charts ⋮ Bicategories of processes ⋮ Two recognizable string-matching problems over free partially commutative monoids ⋮ Distributed Control of Discrete-Event Systems: A First Step ⋮ Petri games: synthesis of distributed systems with causal memory ⋮ Structure of concurrency ⋮ Semicommutations and algebraic languages ⋮ The free partially commutative Lie algebra: Bases and ranks ⋮ String matching problems over free partially commutative monoids ⋮ Unnamed Item ⋮ Compositions de fonctions de commutation partielle ⋮ UNAMBIGUOUS SHARED-MEMORY SYSTEMS ⋮ Compositional synthesis of asynchronous automata ⋮ Time-stamps for Mazurkiewicz traces. ⋮ Mixed languages ⋮ A Nice labelling for tree-like event structures of degree 3 ⋮ A Kleene theorem and model checking algorithms for existentially bounded communicating automata ⋮ Unnamed Item ⋮ Models and logics for true concurrency. ⋮ Unnamed Item ⋮ Kleene Theorems for Product Systems ⋮ Trace monoids with idempotent generators and measure-only quantum automata ⋮ Semi-commutations and rational expressions ⋮ Asynchronous cellular automata for infinite traces ⋮ Realizability of Concurrent Recursive Programs ⋮ Representation of computations in concurrent automata by dependence orders ⋮ Weighted asynchronous cellular automata ⋮ ENFORCING CONCURRENT TEMPORAL BEHAVIORS ⋮ Semi-commutations and Petri nets ⋮ Series-parallel languages and the bounded-width property ⋮ Membership problems for regular and context-free trace languages ⋮ Unnamed Item ⋮ CD-systems of stateless deterministic R(1)-automata governed by an external pushdown store ⋮ Asynchronous cellular automata for pomsets ⋮ Product interval automata ⋮ Distributed automata in an assumption-commitment framework ⋮ A theory of regular MSC languages ⋮ Models for quantitative distributed systems and multi-valued logics ⋮ Bounded time-stamping in message-passing systems ⋮ Atomic semicommutations ⋮ Automated Synthesis: a Distributed Viewpoint ⋮ An extension of Kleene's and Ochmański's theorems to infinite traces ⋮ Kleene Theorems for Synchronous Products with Matching ⋮ Recognizable trace languages, distributed automata and the distribution problem

Cites Work

This page was built for publication: Notes on finite asynchronous automata