We consider five operators on a regular language. Each of them is a tool for constructing a code (respectively prefix, suffix, bifix, infix) and a hypercode out of a given regular language. We give the precise values of the (deterministic) state complexity of these operators: over a constant-size alphabet for the first four of them and over a quadratic-size alphabet for the hypercode operator. © 2011 World Scientific Publishing Company.
State complexity of code operators
Rodaro E.
2011-01-01
Abstract
We consider five operators on a regular language. Each of them is a tool for constructing a code (respectively prefix, suffix, bifix, infix) and a hypercode out of a given regular language. We give the precise values of the (deterministic) state complexity of these operators: over a constant-size alphabet for the first four of them and over a quadratic-size alphabet for the hypercode operator. © 2011 World Scientific Publishing Company.File in questo prodotto:
File | Dimensione | Formato | |
---|---|---|---|
StateComplexityOfCodeOperators (IJFCS).pdf
Accesso riservato
:
Publisher’s version
Dimensione
240.02 kB
Formato
Adobe PDF
|
240.02 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.