Input- or output-unary sweeping transducers are weaker than their 2-way counterparts
| Autor: | Bruno Guillon |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Discrete mathematics
Unary operation General Mathematics 0102 computer and information sciences 02 engineering and technology 01 natural sciences Computer Science Applications Power (physics) Nondeterministic algorithm Transducer 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Cardinality (SQL statements) Software Mathematics |
| Zdroj: | RAIRO - Theoretical Informatics and Applications. 50:275-294 |
| ISSN: | 1290-385X 0988-3754 |
| DOI: | 10.1051/ita/2016028 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|