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)

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 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
PublisherSpringer
Pages134-145
ISBN (Print)3-540-24318-6
DOIs
Publication statusPublished - 2005

Publication series

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

Fingerprint

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

Cite this