Characterizing Languages by Normalization and Termination in String Rewriting

J. Ketema, Jakob Grue Simonsen

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

    94 Downloads (Pure)

    Abstract

    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
    PublisherSpringer
    Pages459-464
    Number of pages6
    ISBN (Electronic)978-3-642-31653-1
    ISBN (Print)978-3-642-31652-4
    DOIs
    Publication statusPublished - Aug 2012

    Publication series

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

    Keywords

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

    Cite this

    Ketema, J., & Simonsen, J. G. (2012). Characterizing Languages by Normalization and Termination in String Rewriting. In H-C. Yen, & O. H. Ibarra (Eds.), Developments in Language Theory: 16th International Conference, DLT 2012, Taipei, Taiwan, August 14-17, 2012. Proceedings (pp. 459-464). (Lecture Notes in Computer Science; Vol. 7410). Berlin, Heidelberg: Springer. https://doi.org/10.1007/978-3-642-31653-1_41