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.[1] 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, Σ, Δ, q0, Fa, Fr) such that (Q, Σ, Δ, q0, Fa) is an NFA, and Fa, Fr are disjoint subsets of Q. For each word w = a1a2 … an, a computation is a sequence of states r0,r1, …, rn, in Q with the following conditions:

  1. r0 = q0
  2. ri+1 ∈ Δ(ri, ai+1), for i = 0, …, n−1.

If rn ∈ Fa then the computation is accepting, and if rn ∈ Fr 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[2] proved that for every SVFA of n states, there exists an equivalent DFA of states. Furthermore, for each positive integer n, there exists an n-state SVFA such that the minimal equivalent DFA has exactly states.

Other results on the state complexity of SVFA were obtained by Jirásková and her colleagues.[3][4]

gollark: Anyway, I'm just simulating it at max speed in incubate mode until the challenge is (hopefully) complete.
gollark: I used a solution off the internet.
gollark: I mean, I did cheat on one of them, since I'm mostly interested in being able to use all the available cells in the sandbox.
gollark: Anyway, my solution for Deception so far consists of a giant wall of glueocytes.
gollark: See, cells actually die after 240 hours in cell lab.

References
  1. Hromkovič, Juraj; Schnitger, Georg (2001). "On the Power of Las Vegas for One-Way Communication Complexity, OBDDs, and Finite Automata". Information and Computation. 169 (2): 284–296. doi:10.1006/inco.2001.3040. ISSN 0890-5401.
  2. Jirásková, Galina; Pighizzini, Giovanni (2011). "Optimal simulation of self-verifying automata by deterministic automata". Information and Computation. 209 (3): 528–535. doi:10.1016/j.ic.2010.11.017. ISSN 0890-5401.
  3. Jirásková, Galina (2016). "Self-Verifying Finite Automata and Descriptional Complexity" (PDF). Descriptional Complexity of Formal Systems. Lecture Notes in Computer Science. 9777. pp. 29–44. doi:10.1007/978-3-319-41114-9_3. ISBN 978-3-319-41113-2. ISSN 0302-9743.
  4. Jirásek, Jozef Štefan; Jirásková, Galina; Szabari, Alexander (2015). "Operations on Self-Verifying Finite Automata". Computer Science -- Theory and Applications. Lecture Notes in Computer Science. 9139. pp. 231–261. doi:10.1007/978-3-319-20297-6_16. ISBN 978-3-319-20296-9. ISSN 0302-9743.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.