Loughborough University
Browse

Once-marking and always-marking 1-limited automata

Download (155.99 kB)
conference contribution
posted on 2024-01-09, 15:51 authored by Giovanni Pighizzini, Luca PrigionieroLuca Prigioniero
Single-tape nondeterministic Turing machines that are allowed to replace the symbol in each tape cell only when it is scanned for the first time are also known as 1-limited automata. These devices characterize, exactly as finite automata, the class of regular languages. However, they can be extremely more succinct. Indeed, in the worst case the size gap from 1-limited automata to one-way deterministic finite automata is double exponential. Here we introduce two restricted versions of 1-limited automata, once-marking 1-limited automata and always-marking 1-limited automata, and study their descriptional complexity. We prove that once-marking 1-limited automata still exhibit a double exponential size gap to one-way deterministic finite automata. However, their deterministic restriction is polynomially related in size to two-way deterministic finite automata, in contrast to deterministic 1-limited automata, whose equivalent two-way deterministic finite automata in the worst case are exponentially larger. For always-marking 1-limited automata, we prove that the size gap to one-way deterministic finite automata is only a single exponential. The gap remains exponential even in the case the given machine is deterministic. We obtain other size relationships between different variants of these machines and finite automata and we present some problems that deserve investigation.

History

School

  • Science

Department

  • Computer Science

Published in

Proceedings of the 16th International Conference on Automata and Formal Languages

Pages

215 - 227

Source

16th International Conference on Automata and Formal Languages (AFL 2023)

Publisher

Open Publishing Association

Version

  • VoR (Version of Record)

Rights holder

© G. Pighizzini & L. Prigioniero

Publisher statement

This is an Open Access Article. It is published by the Open Publishing Association under the Creative Commons Attribution 4.0 International Licence (CC BY). Full details of this licence are available at: https://creativecommons.org/licenses/by/4.0/

Publication date

2023-09-03

Copyright date

2023

ISSN

2075-2180

eISSN

2075-2180

Book series

Electronic Proceedings in Theoretical Computer Science (EPTCS); 386

Language

  • en

Editor(s)

Zsolt Gazdag; Szabolcs Iván; Gergely Kovásznai

Location

Eger, Hungary

Event dates

5th September 2023 - 7th September 2023

Depositor

Dr Luca Prigioniero. Deposit date: 22 December 2023

Usage metrics

    Loughborough Publications

    Categories

    No categories selected

    Keywords

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC