On regular languages over power sets

Tim Fernando, Trinity College Dublin, Ireland


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.



Full Text:


DOI: http://dx.doi.org/10.15398/jlm.v4i1.103

ISSN of the paper edition: 2299-856X