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

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.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11311/1141872
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 4
social impact