3 papers
cs.FL2025
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…
cs.FL2025
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…
cs.FL2025
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…