| Property |
Value |
| dbo:abstract
|
- Die Termersetzungssysteme (TES) sind ein formales Berechnungsmodell in der Theoretischen Informatik. Sie bilden insbesondere die Grundlage der Logik- und funktionalen Programmierung. Ferner spielen sie eine wichtige Rolle beim Wortproblem und bei der Terminierungsanalyse. Termersetzungssysteme sind Mengen von so genannten Termersetzungsregeln. Diese Mengen kann man sich wie Gleichungssysteme zwischen Termen vorstellen, bei dem die Gleichungen nur von links nach rechts angewendet werden dürfen. Beispiel plus(0, y) → y plus(succ(x), y) → succ(plus(x, y)) Die oben stehenden Regeln bilden ein Termersetzungssystem, welches als die Addition zweier natürlicher Zahlen verstanden werden kann. Dies erfordert dass man die Zahl 0 mit dem Term 0, die Zahl 1 mit dem Term succ(0), die Zahl 2 mit dem Term succ(succ(0)) usw. repräsentiert. Die Regeln besagen, dass beispielsweise jedes Vorkommen von in einemTerm durch ersetzt werden darf. Dabei kann selbst ein beliebiger Term sein, muss also insbesondere auch keine natürliche Zahl darstellen. Termersetzungssysteme sind turing-vollständig, stehen also was die Berechnungsstärke angeht anderen Formalismen wie den Turingmaschinen, dem Lambda-Kalkül oder Registermaschinen in nichts nach. Da sie vergleichsweise einfach strukturiert sind und von Computern gut gehandhabt werden können, stellen die Termersetzungssysteme ein wichtiges Hilfsmittel in der computergestützten Analyse von Algorithmen dar. (de)
- Die Termersetzungssysteme (TES) sind ein formales Berechnungsmodell in der Theoretischen Informatik. Sie bilden insbesondere die Grundlage der Logik- und funktionalen Programmierung. Ferner spielen sie eine wichtige Rolle beim Wortproblem und bei der Terminierungsanalyse. Termersetzungssysteme sind Mengen von so genannten Termersetzungsregeln. Diese Mengen kann man sich wie Gleichungssysteme zwischen Termen vorstellen, bei dem die Gleichungen nur von links nach rechts angewendet werden dürfen. Beispiel plus(0, y) → y plus(succ(x), y) → succ(plus(x, y)) Die oben stehenden Regeln bilden ein Termersetzungssystem, welches als die Addition zweier natürlicher Zahlen verstanden werden kann. Dies erfordert dass man die Zahl 0 mit dem Term 0, die Zahl 1 mit dem Term succ(0), die Zahl 2 mit dem Term succ(succ(0)) usw. repräsentiert. Die Regeln besagen, dass beispielsweise jedes Vorkommen von in einemTerm durch ersetzt werden darf. Dabei kann selbst ein beliebiger Term sein, muss also insbesondere auch keine natürliche Zahl darstellen. Termersetzungssysteme sind turing-vollständig, stehen also was die Berechnungsstärke angeht anderen Formalismen wie den Turingmaschinen, dem Lambda-Kalkül oder Registermaschinen in nichts nach. Da sie vergleichsweise einfach strukturiert sind und von Computern gut gehandhabt werden können, stellen die Termersetzungssysteme ein wichtiges Hilfsmittel in der computergestützten Analyse von Algorithmen dar. (de)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageRevisionID
| |
| dct:subject
| |
| rdfs:comment
|
- Die Termersetzungssysteme (TES) sind ein formales Berechnungsmodell in der Theoretischen Informatik. Sie bilden insbesondere die Grundlage der Logik- und funktionalen Programmierung. Ferner spielen sie eine wichtige Rolle beim Wortproblem und bei der Terminierungsanalyse. Termersetzungssysteme sind Mengen von so genannten Termersetzungsregeln. Diese Mengen kann man sich wie Gleichungssysteme zwischen Termen vorstellen, bei dem die Gleichungen nur von links nach rechts angewendet werden dürfen. Beispiel plus(0, y) → y plus(succ(x), y) → succ(plus(x, y)) in einemTerm durch (de)
- Die Termersetzungssysteme (TES) sind ein formales Berechnungsmodell in der Theoretischen Informatik. Sie bilden insbesondere die Grundlage der Logik- und funktionalen Programmierung. Ferner spielen sie eine wichtige Rolle beim Wortproblem und bei der Terminierungsanalyse. Termersetzungssysteme sind Mengen von so genannten Termersetzungsregeln. Diese Mengen kann man sich wie Gleichungssysteme zwischen Termen vorstellen, bei dem die Gleichungen nur von links nach rechts angewendet werden dürfen. Beispiel plus(0, y) → y plus(succ(x), y) → succ(plus(x, y)) in einemTerm durch (de)
|
| rdfs:label
|
- Termersetzungssystem (de)
- Termersetzungssystem (de)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is foaf:primaryTopic
of | |
