一句话：研究无限交替自动机的状态复杂度，将 Karp 状态复杂度框架拓展至超越正则语言的语言类。
本文从自动机理论角度研究有限字语言的复杂度。为超越正则语言类，论文考虑无限自动机，并采用 Karp 定义的状态复杂度来度量语言所需的状态数。核心研究对象是 Chandra、Kozen 和 Stockmeyer 提出的交替自动机：这类机器在输入字上同时运行多个独立计算，并通过布尔组合汇总各计算的结果。论文围绕这一模型，探讨无限交替自动机对非正则语言的状态复杂度刻画，关注交替机制与无限状态如何共同影响语言的可识别性与复杂度。摘要未给出具体定理或上下界，主要贡献在于将状态复杂度问题引入交替自动机这一更强大的计算模型，并为后续刻画非正则语言的状态复杂度提供理论框架。
This paper studies the complexity of languages of finite words using automata theory. To go beyond the class of regular languages, we consider infinite automata and the notion of state complexity defined by Karp. We look at alternating automata as introduced by Chandra, Kozen and Stockmeyer: such machines run independent computations on the word and gather their answers through boolean combinations.
DOI 原文 ·
@inproceedings{paperbot4382,
title = {The State Complexity of Alternating Automata},
author = {Nathanaël Fijalkow},
booktitle = {LICS},
year = {2018},
doi = {10.1145/3209108.3209167}
}