결정론적 다중 시계 타이밍 오토마타 학습

우리는 다중 시계를 가진 결정론적 타이밍 오토마타의 능동 학습을 위한 알고리즘을 제시합니다. 이 알고리즘은 Angluin의 쿼리 프레임워크 안에 있으며, 기존의 결정론적 단일 시계 타이밍 오토마타 능동 학습에 관한 작업에 제안된 아이디어를 따릅니다. 우리는 타이밍 오토마타의 리셋된 시계 언어에 대한 동등성 관계를 도입하고, 학습 문제를 목표 오토마타의 해당 리셋된 시계 언어 학습으로 변환합니다. 리셋된 시계 언어에는 관찰할 수 없는 시계 리셋 정보가 포함되므로, 우리는 학습자가 리셋 정보 쿼리에 응답하여 리셋 정보를 제공할 수 있는 강력한 교사로부터 학습하는 접근 방식을 먼저 제시합니다. 그런 다음, 학습자가 표준 멤버십 쿼리와 동등성 쿼리만 요청할 수 있는 일반 교사 상황에서 알고리즘을 확장하여 학습자가 리셋 정보를 추측하게 합니다. 우리는 학습 알고리즘이 종료되고 올바른 결정론적 타이밍 오토마타를 반환함을 증명합니다. 전환 시 시계가 리셋되는지를 추측해야 하는 필요성으로 인해, 알고리즘은 목표 오토마타의 크기에 대해 지수 복잡성을 가집니다. CCS 개념 • 계산 이론 → 정규 언어; 능동 학습 -