On the state complexity of operations on two-way finite automata
type: Item
instance of: scholarly article
title: On the state complexity of operations on two-way finite automata
zbMATH Open document ID: 1371.68153
author: Galina Jirásková
author: Alexander Okhotin
published in: Information and Computation
publication date: 2017-03-16T00:00:00Z
review text: This contribution discusses the deterministic state complexity of the basic language-theoretic operations on deterministic two-way finite automata. The deterministic state complexity of a language~\(L\) is the least number of states required by such an automaton to recognize \(L\). The basic language-theoretic operations discussed include union, intersection, concatenation, Kleene star, square, projections, reversal, and inverse homomorphism. The state complexity of an operation describes the dependence of the (worst-case) state complexity of the resulting languages in terms of the state complexities of the input languages. Finally, a deterministic two-way automaton is a deterministic Turing machine that cannot modify the tape contents. In other words, it is a finite-state device that processes the input deterministically by moving forward and backward on the tape that contains the input. However, it can only read the tape; information can only be stored in its finitely many states. In detail, this contribution establishes the following state complexities. Suppose that the input languages have state complexity \(m\)~and~\(n\). Then their union has state complexity between \(m + n - o(m+n)\)~and~\(4m + n + c\) for a constant \(c\), their intersection has state complexity between \(m+n-o(m+n)\)~and~\(m+n+1\), their concatenation has state complexity between \(\Omega(\tfrac mn) + \tfrac{2^{\Omega(n)}}{\log m}\)~and~\(2m^{m+1} \cdot 2^{n^{n+1}}\). For Kleene star, square, and projections a state complexity between \(\tfrac 1n2^{\tfrac n2-1}\)~and~\(2^{O(n^{n+1})}\) is reported as well as the rather sharp bounds \(n+1\)~and~\(n+2\) for reversal, and the exact bound~\(2n\) for inverse homomorphism. In all these cases good lower bounds on the size of a deterministic finite automaton are first developed, for which there are established methods. These bounds are then translated by means of the known conversion constructions between deterministic two-way finite automata and d…
reviewed by: Andreas Maletti
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 6695581
zbMATH Keywords: state complexity
zbMATH Keywords: descriptional complexity
zbMATH Keywords: two-way automata
zbMATH Keywords: finite-state automata
zbMATH Keywords: deterministic automata
MaRDI profile type: Publication
full work available at URL: j.ic.2016.12.007
OpenAlex ID: W2560045680
cites work: Partial orders on words, minimal elements of regular languages, and state complexity
cites work: State-complexity of finite-state devices, state compressibility and incompressibility
cites work: State complexity of power
cites work: An alternating hierarchy for finite automata
cites work: Converting two-way nondeterministic unary automata into simpler automata.
cites work: Complementing two-way finite automata
cites work: Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata
cites work: NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
cites work: On a structural property in the state complexity of projected regular languages
cites work: Operations on Unambiguous Finite Automata
cites work: On the State Complexity of Operations on Two-Way Finite Automata
cites work: Mathematical Foundations of Computer Science 2005
cites work: Two-Way Automata versus Logarithmic Space
cites work: Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups
cites work: State Complexity of Union and Intersection for Two-way Nondeterministic Finite Automata
cites work: State complexity of operations on two-way finite automata over a unary alphabet
cites work: Reversibility of Computations in Graph-Walking Automata
cites work: Q5628039
cites work: Optimal simulations between unary automata
cites work: Q5528651
cites work: On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
cites work: Unambiguous finite automata over a unary alphabet
cites work: Q5541339
cites work: The state complexity of \(L^{2}\) and \(L^k\)
cites work: Q5541340
cites work: Lower bounds on the size of sweeping automata
cites work: A note on the reduction of two-way automata to one-way automata
cites work: The state complexities of some basic operations on regular languages
DOI: 10.1016/J.IC.2016.12.007
description: scientific article; zbMATH DE number 6695581