| Issue |
RAIRO-Theor. Inf. Appl.
Volume 50, Number 4, October-December 2016
7th Non-Classical Models of Automata and Applications (NCMA-2015)
|
|
|---|---|---|
| Page(s) | 275 - 294 | |
| DOI | https://doi.org/10.1051/ita/2016028 | |
| Published online | 13 January 2017 | |
Input- or output-unary sweeping transducers are weaker than their 2-way counterparts
LIAFA, Université Paris-Diderot, Paris 7, Paris, France
guillon.bruno+cs@gmail.com
Received: 19 December 2015
Accepted: 16 December 2016
In a previous paper we showed that two-way (nondeterministic) transducers with unary input and output alphabets have the same recognition power as the sweeping ones. We show that this no longer holds when one of the alphabets has cardinality at least 2.
Mathematics Subject Classification: 68Q70
Key words: Unary alphabets / Hadamard relations / two-way / sweeping transducers
© EDP Sciences 2017
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.