Distributed synthesis is simply undecidable

DOI10.1016/J.IPL.2013.11.012MaRDI QIDQ2445907zbMATH OpenOpenAlexFDO

Authors Sven Schewe

Publication date 15 April 2014

Published in Information Processing Letters (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/j.ipl.2013.11.012

zbMATH Keywords

formal methodstemporal logicundecidabilitydistributed synthesis

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Decidability of theories and sets of sentences (03B25) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• On the (High) Undecidability of Distributed Synthesis Problems
• Distributed synthesis for acyclic architectures
• Decidability of well-connectedness for distributed synthesis
• Unlimited Decidability of Distributed Synthesis with Limited Missing Knowledge
• Undecidability in decentralized supervision

Cites work

• scientific article; zbMATH DE number 3492660 (Why is no real title available?)
• scientific article; zbMATH DE number 1142326 (Why is no real title available?)
• scientific article; zbMATH DE number 1754607 (Why is no real title available?)
• scientific article; zbMATH DE number 3237829 (Why is no real title available?)
• scientific article; zbMATH DE number 3189696 (Why is no real title available?)
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Definability in the monadic second-order theory of successor
• Nondeterministic controllers of nondeterministic processes
• On the (High) Undecidability of Distributed Synthesis Problems
• Solving Sequential Conditions by Finite-State Strategies

Cited in

(9)

• On the (High) Undecidability of Distributed Synthesis Problems
• Consensus game acceptors
• Decidability of well-connectedness for distributed synthesis
• Distributed synthesis for parameterized temporal logics
• Distributed PROMPT-LTL synthesis
• Distributed Asynchronous Games With Causal Memory are Undecidable
• Unlimited Decidability of Distributed Synthesis with Limited Missing Knowledge
• Stochastic games with synchronizing objectives
• Undecidability in decentralized supervision

This page was built for publication: Distributed synthesis is simply undecidable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2445907)