Finding finite automata that certify termination of string rewriting systems

A. Geser; D. Hofbauer; J. Waldmann; H. Zantema

doi:10.1142/S0129054105003108

Finding finite automata that certify termination of string rewriting systems

A. Geser, D. Hofbauer, J. Waldmann, H. Zantema

Formal System Analysis

Research output: Contribution to journal › Article › Academic › peer-review

9 Citations (Scopus)

2 Downloads (Pure)

Abstract

We present a technique based on the construction of finite automata to prove termination of string rewriting systems. Using this technique the tools Matchbox and TORPA are able to prove termination of particular string rewriting systems completely automatically for which termination was considered to be very hard until recently.

Original language	English
Pages (from-to)	471-486
Journal	International Journal of Foundations of Computer Science
Volume	16
Issue number	3
DOIs	https://doi.org/10.1142/S0129054105003108
Publication status	Published - 2005

Access to Document

10.1142/S0129054105003108

Cite this

@article{0c7774f78e904c5681b02e4ef4b075ce,

title = "Finding finite automata that certify termination of string rewriting systems",

abstract = "We present a technique based on the construction of finite automata to prove termination of string rewriting systems. Using this technique the tools Matchbox and TORPA are able to prove termination of particular string rewriting systems completely automatically for which termination was considered to be very hard until recently.",

author = "A. Geser and D. Hofbauer and J. Waldmann and H. Zantema",

year = "2005",

doi = "10.1142/S0129054105003108",

language = "English",

volume = "16",

pages = "471--486",

journal = "International Journal of Foundations of Computer Science",

issn = "0129-0541",

publisher = "World Scientific",

number = "3",

}

TY - JOUR

T1 - Finding finite automata that certify termination of string rewriting systems

AU - Geser, A.

AU - Hofbauer, D.

AU - Waldmann, J.

AU - Zantema, H.

PY - 2005

Y1 - 2005

N2 - We present a technique based on the construction of finite automata to prove termination of string rewriting systems. Using this technique the tools Matchbox and TORPA are able to prove termination of particular string rewriting systems completely automatically for which termination was considered to be very hard until recently.

AB - We present a technique based on the construction of finite automata to prove termination of string rewriting systems. Using this technique the tools Matchbox and TORPA are able to prove termination of particular string rewriting systems completely automatically for which termination was considered to be very hard until recently.

U2 - 10.1142/S0129054105003108

DO - 10.1142/S0129054105003108

M3 - Article

SN - 0129-0541

VL - 16

SP - 471

EP - 486

JO - International Journal of Foundations of Computer Science

JF - International Journal of Foundations of Computer Science

IS - 3

ER -

Finding finite automata that certify termination of string rewriting systems

Abstract

Access to Document

Fingerprint

Cite this