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 to deterministic 1-limited automata: while for boolean operations the simulations remain polynomial, for product, star, and reversal they cost exponential in size. The costs for product and star do not reduce if the given machines are sweeping two-way deterministic finite automata. These bounds are tight.

Performing Regular Operations with 1-Limited Automata / G. Pighizzini, L. Prigioniero, Š. Sádovský. - In: THEORY OF COMPUTING SYSTEMS. - ISSN 1432-4350. - (2024), pp. 1-22. [Epub ahead of print] [10.1007/s00224-024-10163-1]

Performing Regular Operations with 1-Limited Automata

G. Pighizzini
Primo
;
2024

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 to deterministic 1-limited automata: while for boolean operations the simulations remain polynomial, for product, star, and reversal they cost exponential in size. The costs for product and star do not reduce if the given machines are sweeping two-way deterministic finite automata. These bounds are tight.
Descriptional complexity; Models of computation; Regular languages;
Settore INF/01 - Informatica
2024
14-mar-2024
https://link.springer.com/article/10.1007/s00224-024-10163-1
Article (author)
File in questo prodotto:
File Dimensione Formato  
s00224-024-10163-1.pdf

accesso aperto

Tipologia: Publisher's version/PDF
Dimensione 518.26 kB
Formato Adobe PDF
518.26 kB Adobe PDF Visualizza/Apri
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/1040850
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact