| Autor: |
Galina Jirásková, Alexander Okhotin |
| Jazyk: |
angličtina |
| Rok vydání: |
2009 |
| Předmět: |
|
| Zdroj: |
Electronic Proceedings in Theoretical Computer Science, Vol 3, Iss Proc. DCFS 2009, Pp 151-161 (2009) |
| Druh dokumentu: |
article |
| ISSN: |
2075-2180 |
| DOI: |
10.4204/EPTCS.3.14 |
| Popis: |
Consider nondeterministic finite automata recognizing base-k positional notation of numbers. Assume that numbers are read starting from their least significant digits. It is proved that if two sets of numbers S and T are represented by nondeterministic automata of m and n states, respectively, then their sum {s+t | s in S, t in T} is represented by a nondeterministic automaton with 2mn+2m+2n+1 states. Moreover, this number of states is necessary in the worst case for all k>=9. |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
