The complexity of two finite-state models, optimizing transducers and counting automata

Thumbnail Image
Date
1988
Authors
Rich, Craig
Major Professor
Advisor
Giora Slutzki
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Organizational Unit
Journal Issue
Is Version Of
Versions
Series
Department
Computer Science
Abstract

An optimizing finite-state transducer is a nondeterministic finite-state transducer in which states are either maximizing or minimizing. In a given state, the optimal output is the maximum or minimum--over all possible transitions--of the transition output concatenated with the optimal output of the resulting state. The ranges of optimizing finite-state transducers form a class in NL which includes a hierarchy based on the number of alternations of maximizing and minimizing states in a computation. The inequivalence problem--whether or not two transducers compute different functions, and the range inequivalence problem are shown to be undecidable. Some other problems associated with this model are shown to be complete for NL and NP;A counting finite-state automaton is a nondeterministic finite-state automaton which, on an input over its input alphabet, (magically) writes in binary the number of accepting computations on the input. We examine the complexity of computing the counting function of an NFA, and the complexity of recognizing its range as a set of binary strings. We also consider the pumping behavior of counting finite-state automata. The class of functions computed by counting NFAs (1) includes a class of functions computed by deterministic finite-state transducers; (2) is contained in the class of functions computed by polynomially time- and linearly space-bounded Turing transducers; (3) includes a function whose range is the composite numbers.

Comments
Description
Keywords
Citation
Source
Subject Categories
Copyright
Fri Jan 01 00:00:00 UTC 1988