10 citations · 28 across the 10 of their papers we have counts for
11 papers
Polynomial Complementation of Nondeterministic 2-Way Finite Automata by 1-Limited Automata
Bruno Guillon, Luca Prigioniero, Javad Taheri
We prove that, paying a polynomial increase in size only, every unrestricted two-way nondeterministic finite automaton (2NFA) can be complemented by a 1-limited automaton (1-LA), a…
Nondeterminism makes unary 1-limited automata concise
Bruno Guillon, Luca Prigioniero, Javad Taheri
We investigate the descriptional complexity of different variants of 1-limited automata (1-las), an extension of two-way finite automata (2nfas) characterizing regular languages. I…
On the Representation and State Complexity of Block Languages
Guilherme Duarte, Nelma Moreira, Luca Prigioniero +1
In this paper, we consider block languages, namely sets of words having the same length, and we propose a new representation for these languages. In particular, given an alphabet o…
Once-Marking and Always-Marking 1-Limited Automata
Giovanni Pighizzini, Luca 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 automat…
Forgetting 1-Limited Automata
Giovanni Pighizzini, Luca Prigioniero
We introduce and investigate forgetting 1-limited automata, which are single-tape Turing machines that, when visiting a cell for the first time, replace the input symbol in it by a…
Magic numbers in periodic sequences
Savinien Kreczman, Luca Prigioniero, Eric Rowland +1
In formal languages and automata theory, the magic number problem can be formulated as follows: for a given integer n, is it possible to find a number d in the range [n,2^n] such t…
Space Complexity of Stack Automata Models
Oscar H. Ibarra, Jozef Jirásek, Ian McQuillan +1
This paper examines several measures of space complexity of variants of stack automata: non-erasing stack automata and checking stack automata. These measures capture the minimum s…
Weight-Reducing Turing Machines
Bruno Guillon, Giovanni Pighizzini, Luca Prigioniero +1
It is well-known that one-tape Turing machines working in linear time are no more powerful than finite automata, namely they recognize exactly the class of regular languages. We pr…
Converting Nondeterministic Two-Way Automata into Small Deterministic Linear-Time Machines
Bruno Guillon, Giovanni Pighizzini, Luca Prigioniero +1
In 1978 Sakoda and Sipser raised the question of the cost, in terms of size of representations, of the transformation of two-way and one-way nondeterministic automata into equivale…
Weakly and Strongly Irreversible Regular Languages
Giovanna J. Lavado, Giovanni Pighizzini, Luca Prigioniero
Finite automata whose computations can be reversed, at any point, by knowing the last k symbols read from the input, for a fixed k, are considered. These devices and their accepted…
Minimal and Reduced Reversible Automata
Giovanna J. Lavado, Giovanni Pighizzini, Luca Prigioniero
A condition characterizing the class of regular languages which have several nonisomorphic minimal reversible automata is presented. The condition concerns the structure of the min…