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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom