Muller message-passing automata and logics

DOI10.1016/j.ic.2008.03.010zbMath1154.68064OpenAlexW1973172637MaRDI QIDQ948076

Dietrich Kuske, Benedikt Bollig

Publication date: 8 October 2008

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2008.03.010

zbMATH Keywords

monadic second-order logicconcurrencyinfinite message sequence chartsmessage-passing automataMuller automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items

An optimal construction of Hanf sentences, Communicating finite-state machines, first-order logic, and star-free propositional dynamic logic, Propositional Dynamic Logic for Message-Passing Systems, Weighted Automata and Logics on Infinite Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Logical definability on infinite traces
• Elements of finite model theory.
• Theories of automata on \(\omega\)-tapes: a simplified approach
• Deterministic asynchronous automata for infinite traces
• Asynchronous cellular automata for pomsets
• Regular sets of infinite message sequence charts
• A Kleene theorem and model checking algorithms for existentially bounded communicating automata
• Message-passing automata are expressively equivalent to EMSO logic
• A generalization of Ehrenfeucht's game and some applications
• A theory of regular MSC languages
• Weak Second‐Order Arithmetic and Finite Automata
• On Communicating Finite-State Machines
• Decision Problems of Finite Automata Design and Related Arithmetics
• Asynchronous cellular automata for infinite traces
• Generalized quantifiers and well orderings