Characterizing languages by normalization and termination in string rewriting

Jeroen Ketema; Jakob Grue Simonsen

doi:10.1007/978-3-642-31653-1_41

Characterizing languages by normalization and termination in string rewriting

Department of Computer Science

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 : 16th International Conference, DLT 2012, Taipei, Taiwan, August 14-17, 2012. Proceedings
Editors	Hsu-Chun Yen, Oscar H. Ibarra
Number of pages	6
Publisher	Springer
Publication date	2012
Pages	459-464
ISBN (Print)	978-3-642-31652-4
ISBN (Electronic)	978-3-642-31653-1
DOIs	https://doi.org/10.1007/978-3-642-31653-1_41
Publication status	Published - 2012
Event	16th International Conference on Developments in Language Theory - Taipei, Taiwan, Province of China Duration: 14 Aug 2012 → 17 Aug 2012 Conference number: 16

Conference

Conference	16th International Conference on Developments in Language Theory
Number	16
Country/Territory	Taiwan, Province of China
City	Taipei
Period	14/08/2012 → 17/08/2012

Series	Lecture notes in computer science
Volume	7410
ISSN	0302-9743

Access to Document

10.1007/978-3-642-31653-1_41

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). Springer. Lecture notes in computer science Vol. 7410 https://doi.org/10.1007/978-3-642-31653-1_41

Characterizing languages by normalization and termination in string rewriting. / Ketema, Jeroen; Simonsen, Jakob Grue.

Developments in Language Theory: 16th International Conference, DLT 2012, Taipei, Taiwan, August 14-17, 2012. Proceedings. ed. / Hsu-Chun Yen; Oscar H. Ibarra. Springer, 2012. p. 459-464 (Lecture notes in computer science, Vol. 7410).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Ketema, J & Simonsen, JG 2012, Characterizing languages by normalization and termination in string rewriting. in H-C Yen & OH Ibarra (eds), Developments in Language Theory: 16th International Conference, DLT 2012, Taipei, Taiwan, August 14-17, 2012. Proceedings. Springer, Lecture notes in computer science, vol. 7410, pp. 459-464, 16th International Conference on Developments in Language Theory , Taipei, Taiwan, Province of China, 14/08/2012. https://doi.org/10.1007/978-3-642-31653-1_41

@inproceedings{fedae328f72b4885b940343b8985fe43,

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 {"}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.",

author = "Jeroen Ketema and Simonsen, {Jakob Grue}",

year = "2012",

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",

note = "16th International Conference on Developments in Language Theory ; Conference date: 14-08-2012 Through 17-08-2012",

}

TY - GEN

T1 - Characterizing languages by normalization and termination in string rewriting

AU - Ketema, Jeroen

AU - Simonsen, Jakob Grue

N1 - Conference code: 16

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-642-31653-1_41

DO - 10.1007/978-3-642-31653-1_41

M3 - Article in proceedings

SN - 978-3-642-31652-4

T3 - Lecture notes in computer science

SP - 459

EP - 464

BT - Developments in Language Theory

A2 - Yen, Hsu-Chun

A2 - Ibarra, Oscar H.

PB - Springer

T2 - 16th International Conference on Developments in Language Theory

Y2 - 14 August 2012 through 17 August 2012

ER -