Equivalence of infinite behavior of finite automata
type: Item
instance of: scholarly article
title: Equivalence of infinite behavior of finite automata
zbMATH Open document ID: 0568.68036
DOI: 10.1016/0304-3975(84)90037-9
author: H. Alaiwan
published in: Theoretical Computer Science
publication date: 1984-01-01T00:00:00Z
review text: Working on an infinite word, a deterministic finite automaton generates a sequence of passed states. We say that a given word is accepted by a given automaton iff the above sequence has infinitely many occurrences of some terminal state. That definition can be easily transferred to non- deterministic automata by adding ''there exists such a sequence of passed states that has...''. Two automata are said to be equivalent iff their sets of accepted words are equal. The well-known Büchi's algorithm for deciding, given two finite automata, upon their equivalence, requires a computational time proportional to \((n^ 2)^{n^ 2}\) where n is the maximal number of states of two given automata. Here a new algorithm is proposed which requires only \(n^ 32^{3n(n+1)}\).
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3907773
zbMATH Keywords: deterministic automata
zbMATH Keywords: algorithm for deciding equivalence
zbMATH Keywords: time complexity
zbMATH Keywords: non-deterministic automata
MaRDI profile type: Publication
full work available at URL: 0304-3975(84)90037-9
OpenAlex ID: W1966870296
cites work: Q5525343
cites work: Q3694724
cites work: Q4079524
cites work: Testing and generating infinite sequences by a finite automaton
cites work: Q5541339
description: scientific article; zbMATH DE number 3907773