arXiv:2605.07758v2 cs.FL

SMT 기반 가중 오토마타 능동 학습

SMT-Based Active Learning of Weighted Automata

Tiago Ferreira, Kevin Batz, Alexandra Silva

제출 2026-09-24

한국어 초록

우리는 Hankel/L* 방식 방법에 대한 실용적이고 견고한 대안으로 비결정적 가중 오토마타(WFA)에 대한 SMT 기반 능동 학습 알고리즘을 제시한다. 우리 알고리즘은 주어진 semiring에 대해 매개변수화되어 있으며, 종료하면 최소 WFA를 생성함이 보장된다. 우리는 부분 정확성을 증명하고 충분한 종료 조건을 제시하며, 이는 특히 모든 유한 semiring에 대해 종료함을 함의한다. 광범위한 실험 평가 결과, 우리 알고리즘은 유한 semiring과 무한 semiring 모두에서 다수의 최소 WFA를 학습할 수 있으며, 순진한 기준선을 크게 능가하고, 최신 알고리즘과 경쟁력 있는 수준을 보이면서도 훨씬 더 작은 오토마타를 생성하고 교사와의 상호작용을 더 적게 요구함을 보여준다.

원문 초록

We present an SMT-based active learning algorithm for nondeterministic weighted automata (WFAs) as a practical and robust alternative to Hankel/L*-style methods. Our algorithm is parametric in a given semiring and, if it terminates, guaranteed to produce minimal WFAs. We prove partial correctness and provide a sufficient termination condition, which in particular implies termination for all finite semirings. Our extensive experimental evaluation shows that our algorithm is capable of learning numerous minimal WFAs over both finite and infinite semirings, vastly outperforms a naive baseline, and is competitive with a state-of-the-art algorithm while producing significantly smaller automata and requiring less interaction with the teacher.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2605.07758v2제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.