Prefix-free languages: left and right quotient and reversal
type: Item
instance of: scholarly article
title: Prefix-free languages: left and right quotient and reversal
zbMATH Open document ID: 1338.68151
author: N. E. Zubov
published in: Theoretical Computer Science
publication date: 2015-12-10T00:00:00Z
review text: This paper discusses the state complexity of the operations ``left quotient'', ``right quotient'', and ``reversal'' for prefix-free regular languages. The state complexity of a language \(L\) is the number of states of the minimal deterministic finite-state automaton accepting \(L\). The state complexity of an operation \(f\) is the worst-case state complexity of the output language \(f(L)\) given the state complexity of the input language \(L\). In other words, given the worst-case input language of state complexity \(n\), what is the state complexity of \(f(L)\) as a function of \(n\). A language is regular if its state complexity is finite (i.e., there is a finite-state automaton accepting it). One of the operations discussed in this paper is the reversal of \(L\), which simply reverses all words in \(L\) and is known to preserve regular languages. The two other operations are actually operations that use two languages \(V\) and \(W\). The left quotient \(V \setminus W = \{w \mid \exists v \in V : vw \in W\}\) and the right quotient \(W / V = \{w \mid \exists v \in V : wv \in W\}\) are binary operations on languages that also preserve regularity. Finally, a language \(L\) is prefix-free if \(v\) is not a prefix of \(w\) for all different words \(v, w \in L\). Given that the alphabet has at least \(n-1\) symbols, where \(n\) is the state complexity of the prefix-free \(W\), the state complexity of the left quotient is \(2^{n-1}\). It is also demonstrated that this size cannot be realized by automata over alphabets of smaller size. The bound for \(n-2\) symbols is \(2^{n-1} - 1\). For alphabet sizes independent of \(n\), a multitude of results is obtained, but some of those remain exponential in \(n\). The right quotient is significantly easier for prefix-free languages and the state complexity is only \(n-1\), which is also proven to be tight in alphabets with at least 2 symbols. Finally, the reversal again introduces an exponential state complexity similar to the…
reviewed by: Andreas Maletti
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 6519457
zbMATH Keywords: state complexity
zbMATH Keywords: determinization
zbMATH Keywords: minimization
zbMATH Keywords: left quotient
zbMATH Keywords: right quotient
zbMATH Keywords: reversal
zbMATH Keywords: regular language
zbMATH Keywords: prefix-free language
zbMATH Keywords: finite automata
MaRDI profile type: Publication
full work available at URL: j.tcs.2015.08.031
OpenAlex ID: W2411905925
cites work: IN SEARCH OF MOST COMPLEX REGULAR LANGUAGES
cites work: State complexity of union and intersection of star on \(k\) regular languages
cites work: Q3655366
cites work: Nondeterministic State Complexity of Basic Operations for Prefix-Free Regular Languages
cites work: State Complexity of Combined Operations for Prefix-Free Regular Languages
cites work: Cyclic Shift on Prefix-Free Languages
cites work: Reversal of binary regular languages
cites work: Succinct representation of regular languages by Boolean automata
cites work: Q5528651
cites work: Q5541339
cites work: On the state complexity of reversals of regular languages
cites work: Q3392273
cites work: Q4714446
cites work: The state complexities of some basic operations on regular languages
DOI: 10.1016/J.TCS.2015.08.031
description: scientific article; zbMATH DE number 6519457