The descriptional complexity of basic operations on regular languages using 1-limited automata, a restricted version of one-tape Turing machines, is investigated. When simulating operations on deterministic finite automata with deterministic 1-limited automata, the sizes of the resulting devices are polynomial in the sizes of the simulated machines. The situation is different when the operations are applied on deterministic 1-limited automata: while for boolean operations the simulations remain polynomial, for product, star, and reversal they cost exponential in size. These bounds are tight.

Performing Regular Operations with 1-Limited Automata / G. Pighizzini, L. Prigioniero, S. Sadovsky (LECTURE NOTES IN COMPUTER SCIENCE). - In: Developments in Language Theory / [a cura di] V. Diekert, M. Volkov. - [s.l] : Springer, 2022. - ISBN 978-3-031-05577-5. - pp. 239-250 (( Intervento presentato al 26. convegno DLT tenutosi a Tampa nel 2022 [10.1007/978-3-031-05578-2_19].

Performing Regular Operations with 1-Limited Automata

G. Pighizzini
Primo
;
L. Prigioniero
Secondo
;
2022

Abstract

The descriptional complexity of basic operations on regular languages using 1-limited automata, a restricted version of one-tape Turing machines, is investigated. When simulating operations on deterministic finite automata with deterministic 1-limited automata, the sizes of the resulting devices are polynomial in the sizes of the simulated machines. The situation is different when the operations are applied on deterministic 1-limited automata: while for boolean operations the simulations remain polynomial, for product, star, and reversal they cost exponential in size. These bounds are tight.
Settore INF/01 - Informatica
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
paper.pdf

embargo fino al 06/05/2023

Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 268.65 kB
Formato Adobe PDF
268.65 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
978-3-031-05578-2_19.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 236.29 kB
Formato Adobe PDF
236.29 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

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: https://hdl.handle.net/2434/939759
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact