Conference paper

Publication year: 2005

Pages: 267-285

Journal: Theoretical Computer Science

Volume number: 330

Issue number: 2

ISSN: 0304-3975

eISSN: 1879-2294

DOI Link: https://doi.org/10.1016/j.tcs.2004.06.030

Conference: Workshop on Descriptional Complexity of Formal Systems

Publisher: Elsevier

Abstract: 
We consider deterministic and nondeterministic finite automata with acceptance conditions that rely on the whole history of a computation on a given word and not only on the last state of the computation under consideration. Formally, these conditions can be seen as the natural analogies of the Buchi and Muller acceptance for finite automata on infinite words. We study the computational power of these new acceptance mechanisms and prove some results on the descriptional complexity of conversions between automata with these new acceptance criteria and finite automata with ordinary acceptance. (C) 2004 Elsevier B.V. All rights reserved.

Harvard Citation style: Holzer, M. and Kutrib, M. (2005) On the descriptional complexity of finite automata with modified acceptance conditions, Theoretical Computer Science, 330(2), pp. 267-285. https://doi.org/10.1016/j.tcs.2004.06.030

APA Citation style: Holzer, M., & Kutrib, M. (2005). On the descriptional complexity of finite automata with modified acceptance conditions. Theoretical Computer Science. 330(2), 267-285. https://doi.org/10.1016/j.tcs.2004.06.030