@inproceedings{4124e834a66742499975bd3f4cfc445c,
title = "Characterizing Languages by Normalization and Termination in String Rewriting",
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 {\textquotedblleft}small‿ alphabet if the rewriting system is allowed access to a {\textquotedblleft}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.",
keywords = "METIS-289712, Context-free grammars, Determinism and nondeterminism, Finite automata, Regular languages, Words",
author = "J. Ketema and Simonsen, \{Jakob Grue\}",
year = "2012",
month = aug,
doi = "10.1007/978-3-642-31653-1\_41",
language = "English",
isbn = "978-3-642-31652-4",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "459--464",
editor = "Hsu-Chun Yen and Ibarra, \{Oscar H.\}",
booktitle = "Developments in Language Theory",
address = "Germany",
note = "16th International Conference on Developments in Language Theory, DLT 2012 ; Conference date: 14-08-2012 Through 17-08-2012",
}