The complexity of two finite-state models, optimizing transducers and counting automata
Date
Authors
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Computer Science—the theory, representation, processing, communication and use of information—is fundamentally transforming every aspect of human endeavor. The Department of Computer Science at Iowa State University advances computational and information sciences through; 1. educational and research programs within and beyond the university; 2. active engagement to help define national and international research, and 3. educational agendas, and sustained commitment to graduating leaders for academia, industry and government.
History
The Computer Science Department was officially established in 1969, with Robert Stewart serving as the founding Department Chair. Faculty were composed of joint appointments with Mathematics, Statistics, and Electrical Engineering. In 1969, the building which now houses the Computer Science department, then simply called the Computer Science building, was completed. Later it was named Atanasoff Hall. Throughout the 1980s to present, the department expanded and developed its teaching and research agendas to cover many areas of computing.
Dates of Existence
1969-present
Related Units
- College of Liberal Arts and Sciences (parent college)
Journal Issue
Is Version Of
Versions
Series
Department
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.