Undecidability in integer weighted finite automata

• Autorzy: Halava V. , Harju T.
• Języki publikacji: EN

Abstrakty

EN

It is shown that the universe problem L(Ag) = A* is undecidable for 4-state finite automata A with integer weight function g on its transitions. This holds even in the case, where A is acyclic and the weighting g satisfies the unimodality condition. The language L(Ag) is defined as the set of words w for which there exists a path p of A having zero weight, that is, g(p) = 0.

Słowa kluczowe

EN

weighted finite automata; universe problem; unimodel

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 1999
• Tom: Vol. 38, Nr 1,2
• Strony: 189--200
• Opis fizyczny: bibliogr. 7 poz.

Twórcy

autor

Halava V.

autor

Harju T.

• Turku Centre for Computer Science TUCS, Lemminkäisenkatu 14A, 4 th floor, FIN-20520 Turku, Finland,