Back to Search
Start Over
Characterizing Languages by Normalization and Termination in String Rewriting
- Source :
- Developments in Language Theory: 16th International Conference, DLT 2012, Taipei, Taiwan, August 14-17, 2012. Proceedings, 459-464, STARTPAGE=459;ENDPAGE=464;TITLE=Developments in Language Theory, Developments in Language Theory ISBN: 9783642316524
- Publication Year :
- 2012
- Publisher :
- Springer, 2012.
-
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.
- Subjects :
- Discrete mathematics
Finite-state machine
Recursively enumerable set
Transitive closure
Determinism and nondeterminism
Context-free grammar
METIS-289712
Regular languages
Words
Combinatorics
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
Regular language
Semi-Thue system
Rewriting
Context-free grammars
Time complexity
Finite automata
Mathematics
Subjects
Details
- Language :
- English
- ISBN :
- 978-3-642-31652-4
- ISBNs :
- 9783642316524
- Database :
- OpenAIRE
- Journal :
- Developments in Language Theory: 16th International Conference, DLT 2012, Taipei, Taiwan, August 14-17, 2012. Proceedings, 459-464, STARTPAGE=459;ENDPAGE=464;TITLE=Developments in Language Theory, Developments in Language Theory ISBN: 9783642316524
- Accession number :
- edsair.doi.dedup.....6c163c5f104a2a2f85ffd9f1744c8e31