String Rewriting Systems

Michał Trybulec

Formalized Mathematics (2007)

  • Volume: 15, Issue: 3, page 121-126
  • ISSN: 1426-2630

Abstract

top
Basing on the definitions from [15], semi-Thue systems, Thue systems, and direct derivations are introduced. Next, the standard reduction relation is defined that, in turn, is used to introduce derivations using the theory from [1]. Finally, languages generated by rewriting systems are defined as all strings reachable from an initial word. This is followed by the introduction of the equivalence of semi-Thue systems with respect to the initial word.

How to cite

top

Michał Trybulec. "String Rewriting Systems." Formalized Mathematics 15.3 (2007): 121-126. <http://eudml.org/doc/266827>.

@article{MichałTrybulec2007,
abstract = {Basing on the definitions from [15], semi-Thue systems, Thue systems, and direct derivations are introduced. Next, the standard reduction relation is defined that, in turn, is used to introduce derivations using the theory from [1]. Finally, languages generated by rewriting systems are defined as all strings reachable from an initial word. This is followed by the introduction of the equivalence of semi-Thue systems with respect to the initial word.},
author = {Michał Trybulec},
journal = {Formalized Mathematics},
language = {eng},
number = {3},
pages = {121-126},
title = {String Rewriting Systems},
url = {http://eudml.org/doc/266827},
volume = {15},
year = {2007},
}

TY - JOUR
AU - Michał Trybulec
TI - String Rewriting Systems
JO - Formalized Mathematics
PY - 2007
VL - 15
IS - 3
SP - 121
EP - 126
AB - Basing on the definitions from [15], semi-Thue systems, Thue systems, and direct derivations are introduced. Next, the standard reduction relation is defined that, in turn, is used to introduce derivations using the theory from [1]. Finally, languages generated by rewriting systems are defined as all strings reachable from an initial word. This is followed by the introduction of the equivalence of semi-Thue systems with respect to the initial word.
LA - eng
UR - http://eudml.org/doc/266827
ER -

References

top
  1. [1] Grzegorz Bancerek. Reduction relations. Formalized Mathematics, 5(4):469-478, 1996. 
  2. [2] Grzegorz Bancerek and Krzysztof Hryniewiecki. Segments of natural numbers and finite sequences. Formalized Mathematics, 1(1):107-114, 1990. 
  3. [3] Czesław Byliński. Finite sequences and tuples of elements of a non-empty sets. Formalized Mathematics, 1(3):529-536, 1990. 
  4. [4] Czesław Byliński. Functions and their basic properties. Formalized Mathematics, 1(1):55-65, 1990. 
  5. [5] Patricia L. Carlson and Grzegorz Bancerek. Context-free grammar - part 1. Formalized Mathematics, 2(5):683-687, 1991. 
  6. [6] Markus Moschner. Basic notions and properties of orthoposets. Formalized Mathematics, 11(2):201-210, 2003. 
  7. [7] Karol Pαk. The Catalan numbers. Part II. Formalized Mathematics, 14(4):153-159, 2006. 
  8. [8] Andrzej Trybulec. Subsets of complex numbers. To appear in Formalized Mathematics. 
  9. [9] Andrzej Trybulec. Binary operations applied to functions. Formalized Mathematics, 1(2):329-334, 1990. 
  10. [10] Andrzej Trybulec. Domains and their Cartesian products. Formalized Mathematics, 1(1):115-122, 1990. 
  11. [11] Andrzej Trybulec. Tarski Grothendieck set theory. Formalized Mathematics, 1(1):9-11, 1990. 
  12. [12] Michał Trybulec. Formal languages - concatenation and closure. Formalized Mathematics, 15(1):11-15, 2007. 
  13. [13] Zinaida Trybulec. Properties of subsets. Formalized Mathematics, 1(1):67-71, 1990. 
  14. [14] Tetsuya Tsunetou, Grzegorz Bancerek, and Yatsuka Nakamura. Zero-based finite sequences. Formalized Mathematics, 9(4):825-829, 2001. 
  15. [15] William M. Waite and Gerhard Goos. Compiler Construction. Springer-Verlag New York Inc., 1984. Zbl0527.68003
  16. [16] Edmund Woronowicz. Relations and their basic properties. Formalized Mathematics, 1(1):73-83, 1990. 
  17. [17] Edmund Woronowicz. Relations defined on sets. Formalized Mathematics, 1(1):181-186, 1990. 
  18. [18] Edmund Woronowicz and Anna Zalewska. Properties of binary relations. Formalized Mathematics, 1(1):85-89, 1990. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.