This paper presents a state-merging algorithm for learning timed languages definable by Event-Recording Automata (ERA) using positive and negative samples in the form of symbolic timed words. Our algorithm, \(\textsf {LEAP}\) (Learning Event-recording Automata Passively), constructs a possibly nondeterministic ERA from such samples based on merging techniques. We prove that determining whether two ERA states can be merged while preserving sample consistency is an \(\textsf{NP}\) -complete problem, and address this with a practical SMT-based solution. Our implementation demonstrates the algorithm’s effectiveness through examples. We also show that every ERA-definable language can be inferred using our algorithm with a suitable sample.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Learning Event-Recording Automata Passively

  • Anirban Majumdar,
  • Sayan Mukherjee,
  • Jean-François Raskin

摘要

This paper presents a state-merging algorithm for learning timed languages definable by Event-Recording Automata (ERA) using positive and negative samples in the form of symbolic timed words. Our algorithm, \(\textsf {LEAP}\) (Learning Event-recording Automata Passively), constructs a possibly nondeterministic ERA from such samples based on merging techniques. We prove that determining whether two ERA states can be merged while preserving sample consistency is an \(\textsf{NP}\) -complete problem, and address this with a practical SMT-based solution. Our implementation demonstrates the algorithm’s effectiveness through examples. We also show that every ERA-definable language can be inferred using our algorithm with a suitable sample.