We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Performing Regular Operations with 1-Limited Automata.
- Authors
Pighizzini, Giovanni; Prigioniero, Luca; Sádovský, Šimon
- 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.
- Subjects
TURING machines; FINITE state machines; PRODUCT costing; POLYNOMIALS
- Publication
Theory of Computing Systems, 2024, Vol 68, Issue 3, p465
- ISSN
1432-4350
- Publication type
Article
- DOI
10.1007/s00224-024-10163-1