17 citations · 53 across the 18 of their papers we have counts for
18 papers
Turn Complexity and Bounded Languages
Giovanni Pighizzini
A turn or reversal in a computation of a pushdown automaton is a switch from a phase in which the height of the pushdown store increases to a phase in which it decreases. Given a p…
Turn Complexity of Context-free Languages, Pushdown Automata and One-Counter Automata
Giovanni Pighizzini
A turn in a computation of a pushdown automaton is a switch from a phase in which the height of the pushdown store increases to a phase in which it decreases. Given a pushdown or o…
Proceedings 14th International Workshop on Non-Classical Models of Automata and Applications (NCMA 2024)
Florin Manea, Giovanni Pighizzini
The Fourteenth International Workshop on Non-Classical Models of Automata and Applications (NCMA 2024) was held in Göttingen, Germany, on August 12 and 13, 2024, at the historic Ge…
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…
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…