Open AccessMonadic Second-Order Logic, Graphs and Unfoldings of Transition Systems
Author(s) -
Bruno Courcelle,
Igor Walukiewicz
Publication year - 1995
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v2i44.19945
Subject(s) - monadic predicate calculus , property (philosophy) , mathematics , order (exchange) , graph , discrete mathematics , combinatorics , transition system , computer science , theoretical computer science , algorithm , higher order logic , finance , economics , description logic , philosophy , epistemology
We prove that every monadic second-order property of the unfolding of a transition system is a monadic second-order property of the system itself. We prove a similar result for certain graph coverings.