Rabin's theorem in the concurrency setting: a conjecture

DOI10.1016/j.tcs.2014.03.010zbMath1308.68085OpenAlexW2087269456WikidataQ123024380 ScholiaQ123024380MaRDI QIDQ2253187

P. S. Thiagarajan, Shaofa Yang

Publication date: 25 July 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.03.010

zbMATH Keywords

monadic second-order logicPetri netevent structureRabin's theoremgrid-freeness

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Decidability of theories and sets of sentences (03B25) Temporal logic (03B44)

Related Items (3)

Medians in median graphs and their cube complexes in linear time ⋮ Distributed Asynchronous Games With Causal Memory are Undecidable ⋮ Kleene Theorems for Synchronous Products with Matching

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The structure of the models of decidable monadic theories of graphs
• Trees, grids, and MSO decidability: from graphs to matroids
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• Graph minors. V. Excluding a planar graph
• Petri nets, event structures and domains. I
• Concrete domains
• Monadic second-order logic on tree-like structures
• On infinite transition graphs having a decidable monadic theory
• The monadic second-order logic of graphs. XV: On a conjecture by D. Seese
• Recurring Dominoes: Making the Highly Undecidable Highly Understandable
• Free Choice Petri Nets
• Mathematical Foundations of Computer Science 2003
• Decidability of Second-Order Theories and Automata on Infinite Trees
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science

This page was built for publication: Rabin's theorem in the concurrency setting: a conjecture