Publikation:

Subtyping for regular tree types : a JAVA-based implementation

Lade...
Vorschaubild

Dateien

hohenadel_thesis.pdf
hohenadel_thesis.pdfGröße: 373.22 KBDownloads: 292

Datum

2003

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

DOI (zitierfähiger Link)
ArXiv-ID

Internationale Patentnummer

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung
Open Access Green
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Masterarbeit/Diplomarbeit
Publikationsstatus
Published

Erschienen in

Zusammenfassung

Ein regulärer Typ r ist ein Subtyp eines regulären Typs s genau dann, wenn die Menge der Instanzen, die r matcht, eine Untermenge der Instanzen ist, die s matcht. Die traditionelle Methode der Subtypprüfung konstruiert für r und s die entsprechenden endlichen Automaten und vergleicht diese. Speziell der Vergleichsschritt ist hierbei typischerweise teuer. Die Arbeit untersucht eine alternative Methode der Subtypprüfung, die einfacher und schneller ist. Der Algorithmus basiert auf der Nutzung eines Termersetzungssystems für reguläre Ausdrücke. Er beginnt mit einer gegebenen regulären Ungleichung, d.h. der Aussage, daß r ein Subtyp von s sei. Diese ist zu beweisen (oder zu widerlegen). Der Algorithmus reduziert r und s durch Termersetzung zu einfacheren Typen, bis eine triviale Prüfung möglich ist, und liefert aufgrund dieser TRUE oder FALSE als Ergebnis. Die Arbeit beschreibt eine prototypische objektorientierte Implementation des Algorithmus in der Sprache JAVA.

Zusammenfassung in einer weiteren Sprache

A regular type r is a subtype of a regular type s iff the set of instances that r matches is a subset of the set of instances that s matches. The traditional method of implementing a subtype check on regular types is to compare the finite automata that correspond to the types. Especially the comparison phase of this subtyping strategy is expensive. The thesis analyzes an alternative approach of subtyping of regular types which is simpler and faster. The algorithm is based on the utilization of a term-rewriting system for regular expressions. It starts with a given regular inequality, i.e. a statement that r is a subtype of s, which is to be proven (or disproven). The algorithm rewrites types r and s to simpler types till only trivial checks remain and eventually returns TRUE or FALSE. The thesis also describes a prototypical object-oriented implementation of the algorithm using the JAVA-language.

Fachgebiet (DDC)
004 Informatik

Schlagwörter

subtyping, antimirov, regular expressions, tree-types, regular types

Konferenz

Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690HOHENADEL, Stefan, 2003. Subtyping for regular tree types : a JAVA-based implementation [Master thesis]
BibTex
@mastersthesis{Hohenadel2003Subty-3510,
  year={2003},
  title={Subtyping for regular tree types : a JAVA-based implementation},
  author={Hohenadel, Stefan}
}
RDF
<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/3510">
    <dc:contributor>Hohenadel, Stefan</dc:contributor>
    <dcterms:issued>2003</dcterms:issued>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dc:format>application/pdf</dc:format>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/3510/1/hohenadel_thesis.pdf"/>
    <dc:language>eng</dc:language>
    <dc:rights>terms-of-use</dc:rights>
    <dcterms:title>Subtyping for regular tree types : a JAVA-based implementation</dcterms:title>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-23T13:46:35Z</dcterms:available>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:creator>Hohenadel, Stefan</dc:creator>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-23T13:46:35Z</dc:date>
    <dcterms:abstract xml:lang="deu">Ein regulärer Typ r ist ein Subtyp eines regulären Typs s genau dann, wenn die Menge der Instanzen, die r matcht, eine Untermenge der Instanzen ist, die s matcht. Die traditionelle Methode der Subtypprüfung konstruiert für r und s die entsprechenden endlichen Automaten und vergleicht diese. Speziell der Vergleichsschritt ist hierbei typischerweise teuer. Die Arbeit untersucht eine alternative Methode der Subtypprüfung, die einfacher und schneller ist. Der Algorithmus basiert auf der Nutzung eines Termersetzungssystems für reguläre Ausdrücke. Er beginnt mit einer gegebenen regulären Ungleichung, d.h. der Aussage, daß r ein Subtyp von s sei. Diese ist zu beweisen (oder zu widerlegen). Der Algorithmus reduziert r und s durch Termersetzung zu einfacheren Typen, bis eine triviale Prüfung möglich ist, und liefert aufgrund dieser TRUE oder FALSE als Ergebnis. Die Arbeit beschreibt eine prototypische objektorientierte Implementation des Algorithmus in der Sprache JAVA.</dcterms:abstract>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/3510/1/hohenadel_thesis.pdf"/>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/3510"/>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
  </rdf:Description>
</rdf:RDF>

Interner Vermerk

xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

Kontakt
URL der Originalveröffentl.

Prüfdatum der URL

Prüfungsdatum der Dissertation

Finanzierungsart

Kommentar zur Publikation

Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Nein
Begutachtet
Diese Publikation teilen