Inequality of finite behaviors of rational weight finite automata is in R
Litow, B. (2003) Inequality of finite behaviors of rational weight finite automata is in R. Information Processing Letters, 87 (3). pp. 139-145.
![[img]](https://researchonline.jcu.edu.au/style/images/fileicons/application_pdf.png) |
PDF (Published Version)
Restricted to Repository staff only |
Abstract
Inequivalence of finite automata accepting finite languages over a non-unary alphabet is NP-complete. However, the inequality of their behaviors does not appear to have been carefully investigated. In the simplest case, the behavior of a finite automaton is the formal series f such that the coefficient f(w) of a word w is the number of distinct accepting computations on w. This notion will be generalized in the paper to finite automata with rational weights. The main result is that inequality of rational weight finite automata with finite behaviors is in R, random polynomial time.
| Item ID: | 534 |
|---|---|
| Item Type: | Article (Research - C1) |
| ISSN: | 1872-6119 |
| Keywords: | Rational weight finite automaton behavior, R, P, Formal polynomial, Formal languages, Computational complexity |
| Additional Information: | © 2003 Elsevier. : This journal is available online - use hypertext links above. |
| Date Deposited: | 03 Nov 2006 |
| FoR Codes: | 08 INFORMATION AND COMPUTING SCIENCES > 0802 Computation Theory and Mathematics > 080299 Computation Theory and Mathematics not elsewhere classified @ 100% |
| SEO Codes: | 89 INFORMATION AND COMMUNICATION SERVICES > 8999 Other Information and Communication Services > 899999 Information and Communication Services not elsewhere classified @ 100% |
| Downloads: |
Total: 4 |
| More Statistics |
Actions (Repository Staff Only)
 |
Item Control Page |