Files in this item



application/pdflopstr-2015-techreport.pdf (482kB)
(no description provided)PDF


Title:Equational Formulas and Pattern Operations in Initial Order-Sorted Algebras
Author(s):Meseguer, José; Skeirik, Stephen
Subject(s):pattern operations, initial decidability, order-sorted logic
Abstract:A pattern, i.e., a term possibly with variables, denotes the set (language) of all its ground instances. In an untyped setting, symbolic operations on finite sets of patterns can represent Boolean operations on languages. But for the more expressive patterns needed in declarative languages supporting rich type disciplines such as subtype polymorphism untyped pattern operations and algorithms break down. We show how they can be properly defined by means of a signature transformation that enriches the types of the original signature. We also show that this transformation allows a systematic reduction of the first-order logic properties of an initial order-sorted algebra supporting subtype-polymorphic functions to equivalent properties of an initial many-sorted (i.e., simply typed) algebra. This yields a new, simple proof of the known decidability of the first-order theory of an initial order-sorted algebra.
Issue Date:2015-06-13
Genre:Technical Report
Sponsor:Partially supported by NSF Grant CNS 13-19109.
Date Available in IDEALS:2015-06-15

This item appears in the following Collection(s)

  • Illinois Research and Scholarship
    This is the default collection for all research and scholarship developed by faculty, staff, or students at the University of Illinois at Urbana-Champaign

Item Statistics