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] PDF (Published Version)
Restricted to Repository staff only

View at Publisher Website: http://dx.doi.org/10.1016/S0020-0190(03)...

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 (Refereed Research - C1)
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.

ISSN: 1872-6119
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%
Citation Count from Web of Science Web of Science 2
Downloads: Total: 1
More Statistics

Actions (Repository Staff Only)

Item Control Page Item Control Page