Weighted automata define a hierarchy of terminating string rewriting systems

Gebhardt Andreas; Waldmann Johannes: Weighted automata define a hierarchy of terminating string rewriting systems. In: Acta cybernetica, (19) 2. pp. 295-312. (2009)

[thumbnail of Gebhardt_2009_ActaCybernetica.pdf]
Előnézet
Cikk, tanulmány, mű
Gebhardt_2009_ActaCybernetica.pdf

Letöltés (175kB) | Előnézet

Absztrakt (kivonat)

The "matrix method" (Hofbauer and Waldmann 2006) proves termination of string rewriting via linear monotone interpretation into the domain of vectors over suitable semirings. Equivalently, such an interpretation is given by a weighted finite automaton. This is a general method that has as parameters the choice of the semiring and the dimension of the matrices (equivalently, the number of states of the automaton). We consider the semirings of nonnegative integers, rationals, algebraic numbers, and reals; with the standard operations and ordering. Monotone interpretations also allow to prove relative termination, which can be used for termination proofs that consist of several steps. The number of steps gives another hierarchy parameter. We formally define the hierarchy and we prove that it is infinite in both directions (dimension and steps).

Mű típusa: Cikk, tanulmány, mű
Befoglaló folyóirat/kiadvány címe: Acta cybernetica
Dátum: 2009
Kötet: 19
Szám: 2
ISSN: 0324-721X
Oldalak: pp. 295-312
Nyelv: angol
Kiadás helye: Szeged
Konferencia neve: Weighted Automata : Theory and Applications (2008) (Dresden)
Befoglaló mű URL: http://acta.bibl.u-szeged.hu/38528/
Kulcsszavak: Számítástechnika, Kibernetika, Automaták
Megjegyzések: Bibliogr.: p. 311-312. ; összefoglalás angol nyelven
Szakterület: 01. Természettudományok
01. Természettudományok > 01.02. Számítás- és információtudomány
Feltöltés dátuma: 2016. okt. 15. 12:25
Utolsó módosítás: 2022. jún. 17. 08:55
URI: http://acta.bibl.u-szeged.hu/id/eprint/12867
Bővebben:
Tétel nézet Tétel nézet