Konferenzpaper

Jahr der Veröffentlichung: 2005

Seiten: 267-285

Zeitschrift: Theoretical Computer Science

Bandnummer: 330

Heftnummer: 2

ISSN: 0304-3975

eISSN: 1879-2294

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

Konferenz: Workshop on Descriptional Complexity of Formal Systems

Verlag: 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-Zitierstil: 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-Zitierstil: 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