17 citations · 24 across the 4 of their papers we have counts for
4 papers
Automata and Reduced Words in the Free Group
Thomas Ang, Giovanni Pighizzini, Narad Rampersad +1
We consider some questions about formal languages that arise when inverses of letters, words and languages are defined. The reduced representation of a language over the free monoi…
Nondeterministic one-tape off-line Turing machines and their time complexity
Giovanni Pighizzini
In this paper we consider the time and the crossing sequence complexities of one-tape off-line Turing machines. We show that the running time of each nondeterministic machine accep…
Deterministic pushdown automata and unary languages
Giovanni Pighizzini
The simulation of deterministic pushdown automata defined over a one-letter alphabet by finite state automata is investigated from a descriptional complexity point of view. We show…
Descriptional complexity of bounded context-free languages
Andreas Malcher, Giovanni Pighizzini
Finite-turn pushdown automata (PDA) are investigated concerning their descriptional complexity. It is known that they accept exactly the class of ultralinear context-free languages…