Self-verifying finite automaton

In automata theory, a self-verifying finite automaton (SVFA)

is a special kind of a nondeterministic finite automaton (NFA)

with a symmetric kind of nondeterminism

introduced by Hromkovič and Schnitger.{{cite journal|last1=Hromkovič|first1=Juraj|last2=Schnitger|first2=Georg|title=On the Power of Las Vegas for One-Way Communication Complexity, OBDDs, and Finite Automata|journal=Information and Computation|volume=169|issue=2|year=2001|pages=284–296|issn=0890-5401|doi=10.1006/inco.2001.3040|doi-access=free}}

Generally, in self-verifying nondeterminism,

each computation path is concluded with any of the three possible answers:

yes, no, and I do not know.

For each input string, no two paths

may give contradictory answers,

namely both answers yes and no on the same input are not possible.

At least one path must give answer yes or no,

and if it is yes then the string is considered accepted.

SVFA accept the same class of languages as deterministic finite automata (DFA)

and NFA but have different state complexity.

Formal definition

An SVFA is represented formally by a 6-tuple,

A=(Q, Σ, Δ, q₀, F_a, F_r)

such that (Q, Σ, Δ, q₀, F_a)

is an NFA,

and F_a, F_r are disjoint subsets of Q.

For each word w = a₁a₂ … a_n,

a computation is a sequence of states

r₀,r₁, …, r_n, in Q with the following conditions:

r₀ = q₀
r_i+1 ∈ Δ(r_i, a_i+1), for i = 0, …, n−1.

If r_n ∈ F_a then the computation is accepting,

and if r_n ∈ F_r then the computation is rejecting.

There is a requirement that for each w

there is at least one accepting computation

or at least one rejecting computation

but not both.

Results

Each DFA is a SVFA, but not vice versa.

Jirásková and Pighizzini{{cite journal|last1=Jirásková|first1=Galina|last2=Pighizzini|first2=Giovanni|title=Optimal simulation of self-verifying automata by deterministic automata|journal=Information and Computation|volume=209|issue=3|year=2011|pages=528–535|issn=0890-5401|doi=10.1016/j.ic.2010.11.017|doi-access=}}

proved that

for every SVFA of n states,

there exists an equivalent DFA

of $g(n)=\Theta(3^{n/3})$ states.

Furthermore, for each positive integer n, there exists an n-state SVFA

such that the minimal equivalent DFA has exactly $g(n)$ states.

Other results on the state complexity of SVFA

were obtained by Jirásková and her colleagues.{{cite book|last1=Jirásková|first1=Galina|title=Descriptional Complexity of Formal Systems|chapter=Self-Verifying Finite Automata and Descriptional Complexity|volume=9777|year=2016|pages=29–44|issn=0302-9743|doi=10.1007/978-3-319-41114-9_3|series=Lecture Notes in Computer Science|isbn=978-3-319-41113-2|chapter-url=https://hal.inria.fr/hal-01633958/file/416473_1_En_3_Chapter.pdf}}{{cite book|last1=Jirásek|first1=Jozef Štefan|title=Computer Science -- Theory and Applications|last2=Jirásková|first2=Galina|last3=Szabari|first3=Alexander|chapter=Operations on Self-Verifying Finite Automata|volume=9139|year=2015|pages=231–261|issn=0302-9743|doi=10.1007/978-3-319-20297-6_16|series=Lecture Notes in Computer Science|isbn=978-3-319-20296-9}}

References

Category:Finite-state machines