### 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 language | English |
---|---|

Title of host publication | Developments in Language Theory |

Subtitle of host publication | 16th International Conference, DLT 2012, Taipei, Taiwan, August 14-17, 2012. Proceedings |

Editors | Hsu-Chun Yen, Oscar H. Ibarra |

Place of Publication | Berlin, Heidelberg |

Publisher | Springer |

Pages | 459-464 |

Number of pages | 6 |

ISBN (Electronic) | 978-3-642-31653-1 |

ISBN (Print) | 978-3-642-31652-4 |

DOIs | |

Publication status | Published - Aug 2012 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer Verlag |

Volume | 7410 |

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