Characterizing Languages by Normalization and Termination in String Rewriting

J. Ketema, Jakob Grue Simonsen

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    167 Downloads (Pure)


    We characterize sets of strings using two central properties from rewriting: normalization and termination. We recall the well-known result that any recursively enumerable set of strings can occur as the set of normalizing strings over a “small‿ alphabet if the rewriting system is allowed access to a “larger‿ alphabet (and extend the result to termination). We then show that these results do not hold when alphabet extension is disallowed. Finally, we prove that for every reasonably well-behaved deterministic time complexity class, there is a set of strings complete for the class that also occurs as the set of normalizing or terminating strings, without alphabet extension.
    Original languageEnglish
    Title of host publicationDevelopments in Language Theory
    Subtitle of host publication16th International Conference, DLT 2012, Taipei, Taiwan, August 14-17, 2012. Proceedings
    EditorsHsu-Chun Yen, Oscar H. Ibarra
    Place of PublicationBerlin, Heidelberg
    Number of pages6
    ISBN (Electronic)978-3-642-31653-1
    ISBN (Print)978-3-642-31652-4
    Publication statusPublished - Aug 2012
    Event16th International Conference on Developments in Language Theory, DLT 2012 - Taipei, Taiwan
    Duration: 14 Aug 201217 Aug 2012

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer Verlag
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Conference16th International Conference on Developments in Language Theory, DLT 2012
    OtherAugust 14-17, 2012


    • METIS-289712
    • Context-free grammars
    • Determinism and nondeterminism
    • Finite automata
    • Regular languages
    • Words

    Cite this