Finding finite automata that certify termination of string rewriting

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)
2 Downloads (Pure)


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 languageEnglish
Title of host publicationImplementation and Application of Automata (Revised Selected Papers, Ninth International Conference, CIAA 2004, Kingston ON, Canada, July 22-24, 2004)
EditorsM. Domaratzki, A. Okhotin, K. Salomaa, S. Yu
Place of PublicationBerlin
ISBN (Print)3-540-24318-6
Publication statusPublished - 2005

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Dive into the research topics of 'Finding finite automata that certify termination of string rewriting'. Together they form a unique fingerprint.

Cite this