Active learning for deterministic bottom-up nominal tree automata

DOI10.1007/978-3-031-17715-6_22MaRDI QIDQ6109488zbMATH OpenOpenAlexFDO

Authors Rindo Nakanishi, Yoshiaki Takata, Hiroyuki Seki

Publication date 28 July 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2208.08319

zbMATH Keywords

active learningmyhill-nerode theoremnominal tree automata

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: Nominal set plays a central role in a group-theoretic extension of finite automata to those over an infinite set of data values. Moerman et al. proposed an active learning algorithm for nominal word automata with the equality symmetry. In this paper, we introduce deterministic bottom-up nominal tree automata (DBNTA), which operate on trees whose nodes are labelled with elements of an orbit finite nominal set. We then prove a Myhill-Nerode theorem for the class of languages recognized by DBNTA and propose an active learning algorithm for DBNTA. The algorithm can deal with any data symmetry that admits least support, not restricted to the equality symmetry and/or the total order symmetry. To prove the termination of the algorithm, we define a partial order on nominal sets and show that there is no infinite chain of orbit finite nominal sets with respect to this partial order between any two orbit finite sets.

Cites work

• A fresh approach to learning register automata
• A new approach to abstract syntax with variable binding
• Active learning for deterministic bottom-up nominal tree automata
• Active learning for extended finite state machines
• Automata theory in nominal sets
• Complexity results on register context-free grammars and register tree automata
• Context-free languages over infinite alphabets
• Finite state machines for strings over infinite alphabets
• Finite-memory automata
• scientific article; zbMATH DE number 5999538 (Why is no real title available?)
• scientific article; zbMATH DE number 1956591 (Why is no real title available?)
• scientific article; zbMATH DE number 1418458 (Why is no real title available?)
• Intractability of decision problems for finite-memory automata
• Learning context-free grammars from structural data in polynomial time
• Learning Meets Verification
• Learning nominal automata
• Learning regular sets from queries and counterexamples
• LTL with the freeze quantifier and register automata
• Model checking
• Reachability in pushdown register automata
• Reactive synthesis from visibly register pushdown automata
• Regular expressions for data words
• Tree Automata over Infinite Alphabets
• Two-variable logic on data words

Cited in

(3)

• Active learning for deterministic bottom-up nominal tree automata
• Automata and grammars for data words
• Active learning for extended finite state machines

This page was built for publication: Active learning for deterministic bottom-up nominal tree automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6109488)