Mirror images and schemes for the maximal complexity of nondeterminism
type: Item
instance of: scholarly article
zbMATH Open document ID: 1294.68105
publication date: 2012-06-20T00:00:00Z
full work available at URL: fulltext.html
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q19
Mathematics Subject Classification ID: 68Q70
zbMATH DE Number: 6048143
zbMATH Keywords: finite automaton
zbMATH Keywords: deterministic finite automaton
zbMATH Keywords: descriptional complexity
zbMATH Keywords: mirror image
zbMATH Keywords: reversal
zbMATH Keywords: automaton scheme
author: Arto Salomaa
MaRDI profile type: Publication
Recommended article: Undecidability of State Complexities Using Mirror Images
Recommended article: Refining Nondeterminism in Relativizations of Complexity Classes
Recommended article: Q3356301
Recommended article: Q4501542
Recommended article: Q3746888
Recommended article: Q3197314
Recommended article: Nondeterministics circuits, space complexity and quasigroups
Recommended article: Q3747727
Recommended article: Completeness for nondeterministic complexity classes
Recommended article: On limited nondeterminism and the complexity of the V-C dimension
title: Mirror images and schemes for the maximal complexity of nondeterminism
published in: Fundamenta Informaticae
review text: The contribution investigates when the subset construction, which given a finite automaton constructs an equivalent deterministic finite automaton, induces the maximal, exponential blow-up. More precisely, the author investigates schemes of deterministic finite automata, whose reversal, which in general is a potentially non-deterministic finite automaton accepting the mirror image of the language accepted by the original automaton, yields the mentioned maximal blow-up when used in the subset construction. A scheme here is a general automaton layout description (given the number \(n\) of states it specifies the transitions between the states), in which the selection of the initial state and the selection of the final states is left open. In fact, such schemes are investigated such that for any (non-trivial) selection of the initial state and the final states we obtain a maximal blow-up.NEWLINENEWLINEThe author presents an algebraic approach to this problem. He first recalls the 3-symbol Lupanov automaton, which was the inspiration for many of the subsequently discovered automata that induce the maximal blow-up. For this case (with at least 3 symbols) solutions to the maximal blow-up problem for schemes are essentially known and quickly recalled. Then the author develops an algebraic theory that explains why the maximal blow-up occurs. In particular, it reduces the maximal blow-up problem for schemes to the completeness of a set of subset functions. This part is rather straightforward, but translates the problem into a new setting. This theory is then applied to the binary case which was still partially open. The obtained complete set of subset functions thus yields a scheme over a binary alphabet that induces the maximal blow-up. Finally, the author recalls an existing approach jointly with the late Derrick Wood [\textit{A. Salomaa} et al., Theor. Comput. Sci. 320, No. 2--3, 315--329 (2004; Zbl 1068.68078)]. This proposal already yields a partial solution, which is a…
reviewed by: Andreas Maletti
description: scientific article; zbMATH DE number 6048143