| 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 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 turingvollstä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)
- En las matemáticas, ciencias de la computación y la lógica, la reescritura incluye una amplia gama de métodos para reemplazar subtérminos de una fórmula con otros términos. Tales métodos pueden lograrse por sistemas de reescritura (también conocidos como motores de reescritura o sistemas de reducción). En su forma más básica, consisten en un conjunto de objetos, además de relaciones representando funciones para transformar tales objetos. Puede que reescritura sea no determinista. Puede que una regla para reescribir un término pueda aplicarse de muchas maneras diferentes a dicho término, o que puedan aplicarse más de una regla. Los sistemas de reescritura no proveen un algoritmo para cambiar un término por otro, sino un conjunto de posibles aplicaciones de reglas. Sin embargo, cuando se combinan con un algoritmo apropiado, los sistemas de reescritura pueden verse como programas informáticos, y varios programas para demostrar teoremas y lenguajes de programación declarativa se basan en la reescritura de términos. (es)
- In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a formula with other terms. Such methods may be achieved by rewriting systems (also known as rewrite systems, rewrite engines, or reduction systems). In their most basic form, they consist of a set of objects, plus relations on how to transform those objects. Rewriting can be non-deterministic. One rule to rewrite a term could be applied in many different ways to that term, or more than one rule could be applicable. Rewriting systems then do not provide an algorithm for changing one term to another, but a set of possible rule applications. When combined with an appropriate algorithm, however, rewrite systems can be viewed as computer programs, and several theorem provers and declarative programming languages are based on term rewriting. (en)
- En informatique théorique, la réécriture (ou récriture) est un modèle de calcul dans lequel il s’agit de transformer des objets syntaxiques (mots, termes, lambda-termes, programmes, preuves, graphes, etc.) en appliquant des règles bien précises. La réécriture est utilisée en informatique, en algèbre, en logique mathématique et en linguistique. La réécriture est utilisée en pratique pour la gestion des courriers électroniques (dans le logiciel sendmail, les entêtes de courrier sont manipulées par des systèmes de réécriture) ou la génération et l'optimisation de code dans les compilateurs. (fr)
- In matematica, informatica e logica, la riscrittura è la sostituzione di un oggetto al posto di una parte di un altro oggetto, secondo una precisa regola formale. Un sistema di riscrittura è appunto costituito da un insieme di oggetti, per esempio termini, grafi o altri oggetti matematici, e un insieme finito di regole che definiscono una relazione sugli oggetti. Quando un sistema di riscrittura permette, dato un oggetto, di applicare diverse regole, è chiamato non deterministico e talvolta integrato da una strategia di scelta. Quest'ultimo caso è particolarmente interessante nella teoria dei linguaggi di programmazione, perché diversi linguaggi dichiarativi (funzionali o logici) sono studiati come sistemi di riscrittura di termini. (it)
- 수학, 컴퓨터 과학 및 논리학에서 재작성은 다양한 부분을 다루고 있다. (특별히 비결정적인 부분에서 중요하다) 이는 부분식을 다른 항으로 교체하여 이루어진다. 재작성 시스템에서 다루는 것은 물체들의 집합과 그들 간의 관계 및 변환이다. 재작성은 비결정적일 수 있다. 한 구문(term)을 작성하는 하나의 규칙은 여러 가지 방법으로 해당 구문에 적용될 수 있다. 또한 복수의 규칙이 적용될 수도 있다. 재작성 시스템은 하나의 구문을 다른 구문으로 수정하는 알고리즘을 제공하는 것이 아니라 여러 규칙을 묶어 제공한다. 적절한 알고리즘을 구성하는 규칙들의 집합은 컴퓨터 프로그램 그 자체 혹은 몇몇 항 재작성(term-rewriting) 기반 선언 프로그래밍 언어로 간주되기도 한다. (ko)
- 項書き換え（こうかきかえ、英: term rewriting）とは、数学・計算機科学・論理学において、式（数式、論理式）の項を別の項に置換する手法を総称する用語である。項書き換え系（英: term rewriting system、TRS）とは、項の集合とその置換規則から構成される。 項書き換えは非決定的になることがありうる。ある規則で書き換え可能な項が他の規則でも書き換え可能な場合がありえて、その場合は複数の規則が適用可能と言うことになる。項書き換え系では、項書き換えのためのアルゴリズムは提供されず、書き換え規則の集合のみが提供される。しかし、適当なアルゴリズムと組み合わせれば、項書き換え系はプログラムのような働きをし、実際いくつかの宣言型プログラミング言語は項書き換えに基づいている。 (ja)
- In de theoretische informatica is herschrijven (Engels: rewriting) een onderzoeksgebied dat zich bezighoudt met stapsgewijze, discrete transformaties van objecten, vaak met het doel een bepaald eindresultaat (bijvoorbeeld de uitkomst van een berekening) te bereiken. De mogelijke stappen die genomen kunnen worden, worden gespecificeerd in een herschrijfsysteem. Herschrijfsystemen zijn vaak niet-deterministisch: het wordt niet voorgeschreven welke van de mogelijke stappen de volgende stap is. Er bestaan verschillende vormen van herschrijven, bijvoorbeeld termherschrijven, graafherschrijven en stringherschrijven. (nl)
- Переписывание — широкий спектр техник, методов и теоретических результатов, связанных с процедурами последовательной замены частей формул или термов формального языка по заданной схеме — системе переписывающих правил. В наиболее общей форме речь идёт о совокупности некоторого набора объекта и правил — отношений между этими объектами, которые указывают как преобразовать этот набор. Переписывание может быть недетерминированным. Например, система переписывающих правил может включать в себя правило, которое может быть применено к одному и тому же терму несколькими разными способами, но не содержать, при этом, указания на то, какой конкретно способ нужно применить в том или ином случае. Если система переписывания, всё же, оформлена в качестве однозначно понимаемого алгоритма, она может рассматриваться как компьютерная программа. На техниках переписывания основан ряд систем интерактивного доказательства теорем и декларативных языков программирования. (ru)
- Em matemática um sistema de redução é um sistema onde termos podem ser reescritos usando uma lista finita, ou infinita, de regras de reescrita Exemplos de sistemas de redução incluem sistemas de reescrita de cadeias de caractere, sistemas de reescrita de termos, cálculo lambda sob e . Quando nenhuma regra de redução pode ser aplicada para uma determinada expressão, é dito que esta está na Forma Normal. (pt)
- У математиці, комп'ютерній науці та в логіці термін рерайтинг (англ. rewriting) означає широкий діапазон способів (потенційно не детермінованих) заміни елементів формули таким чином, що зміст не міняється. У самому базовому вигляді системи рерайтинга складаються з набору об'єктів, плюс відносин про те, як перетворити ці об'єкти. Рерайтинг може бути недетермінованим. Одне правило рерайтинга терму може застосовуватися багатьма різними способами до цього терму, або може бути застосовано більше одного правила. Тоді системи рерайтинга не забезпечують алгоритм зміни одного терму на інший, але забезпечують набір можливих правил програми. Проте у поєднанні з відповідним алгоритмом системи рерайтинга можуть розглядатися як комп'ютерні програми, на рерайтингу термів засновано декілька систем доведення теорем та декларативних мов програмування. (uk)
- 重写逻辑是一种对绝大多数编程语言和系统进行规范描述的计算机逻辑。重写逻辑能把目标逻辑的抽象语法表示为代数结构。利用重写规则，目标逻辑的推理规则可以被描述出来。 重写逻辑中的语法和结构化公理都由用户自己定义，这使其变得极为简单且通用。 1992年，José Meseguer在《作为统一并发模型的条件重写逻辑》一文中首先提出重写逻辑这一概念。 (zh)
|
| rdfs:comment
|
- En informatique théorique, la réécriture (ou récriture) est un modèle de calcul dans lequel il s’agit de transformer des objets syntaxiques (mots, termes, lambda-termes, programmes, preuves, graphes, etc.) en appliquant des règles bien précises. La réécriture est utilisée en informatique, en algèbre, en logique mathématique et en linguistique. La réécriture est utilisée en pratique pour la gestion des courriers électroniques (dans le logiciel sendmail, les entêtes de courrier sont manipulées par des systèmes de réécriture) ou la génération et l'optimisation de code dans les compilateurs. (fr)
- 수학, 컴퓨터 과학 및 논리학에서 재작성은 다양한 부분을 다루고 있다. (특별히 비결정적인 부분에서 중요하다) 이는 부분식을 다른 항으로 교체하여 이루어진다. 재작성 시스템에서 다루는 것은 물체들의 집합과 그들 간의 관계 및 변환이다. 재작성은 비결정적일 수 있다. 한 구문(term)을 작성하는 하나의 규칙은 여러 가지 방법으로 해당 구문에 적용될 수 있다. 또한 복수의 규칙이 적용될 수도 있다. 재작성 시스템은 하나의 구문을 다른 구문으로 수정하는 알고리즘을 제공하는 것이 아니라 여러 규칙을 묶어 제공한다. 적절한 알고리즘을 구성하는 규칙들의 집합은 컴퓨터 프로그램 그 자체 혹은 몇몇 항 재작성(term-rewriting) 기반 선언 프로그래밍 언어로 간주되기도 한다. (ko)
- 項書き換え（こうかきかえ、英: term rewriting）とは、数学・計算機科学・論理学において、式（数式、論理式）の項を別の項に置換する手法を総称する用語である。項書き換え系（英: term rewriting system、TRS）とは、項の集合とその置換規則から構成される。 項書き換えは非決定的になることがありうる。ある規則で書き換え可能な項が他の規則でも書き換え可能な場合がありえて、その場合は複数の規則が適用可能と言うことになる。項書き換え系では、項書き換えのためのアルゴリズムは提供されず、書き換え規則の集合のみが提供される。しかし、適当なアルゴリズムと組み合わせれば、項書き換え系はプログラムのような働きをし、実際いくつかの宣言型プログラミング言語は項書き換えに基づいている。 (ja)
- Em matemática um sistema de redução é um sistema onde termos podem ser reescritos usando uma lista finita, ou infinita, de regras de reescrita Exemplos de sistemas de redução incluem sistemas de reescrita de cadeias de caractere, sistemas de reescrita de termos, cálculo lambda sob e . Quando nenhuma regra de redução pode ser aplicada para uma determinada expressão, é dito que esta está na Forma Normal. (pt)
- 重写逻辑是一种对绝大多数编程语言和系统进行规范描述的计算机逻辑。重写逻辑能把目标逻辑的抽象语法表示为代数结构。利用重写规则，目标逻辑的推理规则可以被描述出来。 重写逻辑中的语法和结构化公理都由用户自己定义，这使其变得极为简单且通用。 1992年，José Meseguer在《作为统一并发模型的条件重写逻辑》一文中首先提出重写逻辑这一概念。 (zh)
- 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 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)) (de)
- En las matemáticas, ciencias de la computación y la lógica, la reescritura incluye una amplia gama de métodos para reemplazar subtérminos de una fórmula con otros términos. Tales métodos pueden lograrse por sistemas de reescritura (también conocidos como motores de reescritura o sistemas de reducción). En su forma más básica, consisten en un conjunto de objetos, además de relaciones representando funciones para transformar tales objetos. (es)
- In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a formula with other terms. Such methods may be achieved by rewriting systems (also known as rewrite systems, rewrite engines, or reduction systems). In their most basic form, they consist of a set of objects, plus relations on how to transform those objects. (en)
- In matematica, informatica e logica, la riscrittura è la sostituzione di un oggetto al posto di una parte di un altro oggetto, secondo una precisa regola formale. Un sistema di riscrittura è appunto costituito da un insieme di oggetti, per esempio termini, grafi o altri oggetti matematici, e un insieme finito di regole che definiscono una relazione sugli oggetti. Quando un sistema di riscrittura permette, dato un oggetto, di applicare diverse regole, è chiamato non deterministico e talvolta integrato da una strategia di scelta. (it)
- In de theoretische informatica is herschrijven (Engels: rewriting) een onderzoeksgebied dat zich bezighoudt met stapsgewijze, discrete transformaties van objecten, vaak met het doel een bepaald eindresultaat (bijvoorbeeld de uitkomst van een berekening) te bereiken. De mogelijke stappen die genomen kunnen worden, worden gespecificeerd in een herschrijfsysteem. Herschrijfsystemen zijn vaak niet-deterministisch: het wordt niet voorgeschreven welke van de mogelijke stappen de volgende stap is. (nl)
- Переписывание — широкий спектр техник, методов и теоретических результатов, связанных с процедурами последовательной замены частей формул или термов формального языка по заданной схеме — системе переписывающих правил. В наиболее общей форме речь идёт о совокупности некоторого набора объекта и правил — отношений между этими объектами, которые указывают как преобразовать этот набор. (ru)
- У математиці, комп'ютерній науці та в логіці термін рерайтинг (англ. rewriting) означає широкий діапазон способів (потенційно не детермінованих) заміни елементів формули таким чином, що зміст не міняється. У самому базовому вигляді системи рерайтинга складаються з набору об'єктів, плюс відносин про те, як перетворити ці об'єкти. (uk)
|
