• Login
    View Item 
    •   Home
    • Graduate Theses, Dissertations and Projects
    • Queen's Graduate Theses and Dissertations
    • View Item
    •   Home
    • Graduate Theses, Dissertations and Projects
    • Queen's Graduate Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Distances Between Languages: Algorithms and Descriptional Complexity

    Thumbnail
    View/Open
    Ng_Timothy_201708_PhD.pdf (845.5Kb)
    Author
    Ng, Timothy
    Metadata
    Show full item record
    Abstract
    We consider the descriptional complexity of neighbourhoods of regular languages and the computational complexity of computing the distance between languages. Distance measures are defined on words to describe their similarity. These measures can be extended to languages, which are sets of words. We consider several different notions of distance measures on languages.

    The neighbourhood of a language L is the set of words within some fixed distance of a word in L. We show that we can construct weighted finite automata for neighbourhoods of regular languages with respect to additive quasi-distances. We consider the state complexity of the neighbourhoods and the state complexity of approximate pattern matching. We establish a tight state complexity lower bound for the edit distance neighbourhood of a language recognized by a deterministic finite automaton.

    We consider the deterministic and nondeterministic state complexity of prefix, suffix, and subword distance neighbourhoods. We establish tight deterministic state complexity bounds for the prefix and suffix distance neighbourhoods of regular languages and of finite languages. For prefix distance neighbourhoods, we consider prefix-convex subclasses of regular languages. We also establish the state complexity of suffix neighbourhoods of suffix-closed languages. We give an upper bound for the state complexity of the subword distance neighbourhood of a regular language.

    Based on the edit distance algorithms of Mohri and Han and co-authors, we give algorithms for computing the prefix distance between two regular languages, a context-free language and a regular language, and two visibly pushdown languages. We extend these algorithms to compute the inner prefix distance of regular languages and visibly pushdown languages.

    We give algorithms to compute the relative prefix distance of two regular languages. For a given integer k, we show that for a deterministic context-free language and a regular language or for two visibly pushdown languages, it is decidable whether their relative prefix distance is at most k. This is very close to the borderline between decidable and undecidable since, on the other hand, we show that deciding the same question for a deterministic context-free language and a visibly pushdown language is undecidable.
    URI for this record
    http://hdl.handle.net/1974/22018
    Collections
    • School of Computing Graduate Theses
    • Queen's Graduate Theses and Dissertations
    Request an alternative format
    If you require this document in an alternate, accessible format, please contact the Queen's Adaptive Technology Centre

    DSpace software copyright © 2002-2015  DuraSpace
    Contact Us
    Theme by 
    Atmire NV
     

     

    Browse

    All of QSpaceCommunities & CollectionsPublished DatesAuthorsTitlesSubjectsTypesThis CollectionPublished DatesAuthorsTitlesSubjectsTypes

    My Account

    LoginRegister

    Statistics

    View Usage StatisticsView Google Analytics Statistics

    DSpace software copyright © 2002-2015  DuraSpace
    Contact Us
    Theme by 
    Atmire NV