本文研究一维及二维细胞自动机（CA）的归纳推断问题，即根据有限数量的可用数据推断出一个与之兼容的CA。此处的数据以有限个区间的形式给出，每个区间由状态集字母表上的两个字w和w'以及一个正整数i组成。推断目标是构造一个CA，使其对每个区间(w, w', i)均兼容，即该CA能在i步内由w导出w'。我们考虑该问题的三种变体：1）CA完全预先已知，目标为验证其兼容性；2）CA部分预先已知，目标为将其扩展为一个完整的、兼容的CA；3）CA完全未知，目标为在存在解的前提下完整构造一个兼容的CA。对于全部三种变体，推断均可在多项式时间内完成，且该问题属于P-完全问题。

Inductive inference of one- and two-way cellular automata (CA) is considered. This involves inferring a CA that is compatible with a finite amount of available data. In this paper, this information is provided in the form of a finite set of intervals, where each interval consists of two words w and w' over a state set alphabet, with a positive integer i. The goal is to infer a CA which is compatible with each interval (w,w',i), meaning that it can derive w' from w in i steps. We consider three variations of this problem, 1) where the CA is completely known a priori, and the goal is therefore to verify compatibility, 2) where the CA is partially known a priori and the goal is to extend it to a full CA that is compatible, and 3) where the CA is completely unknown, and the goal is to fully construct one that is compatible if one exists. With all three variations, inference can be completed in polynomial time, and is in fact P-complete.