Performing regular operations with 1-limited automata

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...

Full description

Bibliographic Details

Main Authors:	Giovanni Pighizzini, Luca Prigioniero, Šimon Sádovský
Format:	Default Article
Published:	2024
Subjects:	Distributed computing and systems software Theory of computation Applied mathematics Computation Theory & Mathematics Models of computation Regular languages
Online Access:	https://hdl.handle.net/2134/27645765.v1
Tags:	Add Tag No Tags, Be the first to tag this record!