On regular languages over power sets

Abstract

The power set of a finite set is used as the alphabet of a
string interpreting a sentence of Monadic Second-Order Logic so that
the string can be reduced (in a straightforward way) to the symbols
occurring in the sentence. Simple extensions to regular expressions
are described matching the succinctness of Monadic Second-Order
Logic. A link to Goguen and Burstall’s notion of an institution is
forged, and applied to conceptions within natural language semantics
of time based on change.