On the boundary of regular languages
type: Item
instance of: scholarly article
title: On the boundary of regular languages
zbMATH Open document ID: 1317.68098
author: Yanyan Li
published in: Theoretical Computer Science
publication date: 2015-05-18T00:00:00Z
review text: This paper considers the computation of the boundary of a regular language, defined as the intersection of the Kleene star of this language with the Kleene star of its complement. The precise state complexity of the boundary of a regular language is found. The upper bound is obtained by counting unreachable states in the automaton produced using standard constructions for Kleene star and intersection, and it is proved that this upper bound can be reached by automata over a five-letter alphabet. A precise bound in the case of a four-letter alphabet and asymptotic bounds for two- and three-letter alphabets are also provided.
reviewed by: Michal Kunc
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 6436196
zbMATH Keywords: regular language
zbMATH Keywords: boundary
zbMATH Keywords: deterministic finite automaton
zbMATH Keywords: state complexity
MaRDI profile type: MaRDI publication profile
full work available at URL: j.tcs.2015.01.022
OpenAlex ID: W2146264489
cites work: CLOSURES IN FORMAL LANGUAGES AND KURATOWSKI'S THEOREM
cites work: The Kuratowski Closure-Complement Problem
cites work: The State Complexity of Star-Complement-Star
cites work: Q5628039
cites work: Q5541339
cites work: State complexity of combined operations
cites work: Q3392273
cites work: Q4714446
cites work: The state complexities of some basic operations on regular languages
DOI: 10.1016/J.TCS.2015.01.022
description: scientific article; zbMATH DE number 6436196