9 papers
Construction of a DFA for Computing Grundy Numbers in the Successful Derivation Games on Right-Linear Grammars
Yoshiaki Takata, Yusuke Inoue, Hiroyuki Seki
Inoue et al. have introduced the successful derivation game (SDG) on context-free grammars (CFGs), which is a generalization of classic heap-based games including subtraction games…
Complexity of the Existence of Constrained Secure Equilibria in Multi-Player Games
Hiroki Mizuno, Yoshiaki Takata, Hiroyuki Seki
We consider a multi-player non-zero-sum turn-based game (abbreviated as multi-player game) on a finite directed graph. A secure equilibrium (SE) is a strategy profile in which no p…
Non-cooperative rational synthesis problem for probabilistic strategies
So Koide, Yoshiaki Takata, Hiroyuki Seki
We study the decidability and complexity of non-cooperative rational synthesis problem (abbreviated as NCRSP) for some classes of probabilistic strategies. We show that NCRSP for s…
Verification with Common Knowledge of Rationality for Graph Games
Rindo Nakanishi, Yoshiaki Takata, Hiroyuki Seki
Realizability asks whether there exists a program satisfying its specification. In this problem, we assume that each agent has her own objective and behaves rationally to satisfy h…
A Subclass of Mu-Calculus with the Freeze Quantifier Equivalent to Buchi Register Automata
Yoshiaki Takata, Akira Onishi, Ryoma Senda +1
Register automaton (RA) is an extension of finite automaton for dealing with data values in an infinite domain. In the previous work, we proposed disjunctive mu-calcul…
A game-theoretic approach to indistinguishability of winning objectives as user privacy
Rindo Nakanishi, Yoshiaki Takata, Hiroyuki Seki
Game theory on graphs is a basic tool in computer science. In this paper, we propose a new game-theoretic framework for studying the privacy protection of a user who interactively…
Active Learning for Deterministic Bottom-up Nominal Tree Automata
R. Nakanishi, Y. Takata, H. Seki
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 algorith…
Reduction of Register Pushdown Systems with Freshness Property to Pushdown Systems in LTL Model Checking
Yoshiaki Takata, Ryoma Senda, Hiroyuki Seki
Pushdown systems (PDS) are known as an abstract model of recursive programs, and model checking methods for PDS have been studied. Register PDS (RPDS) are PDS augmented by register…
Complexity Results on Register Pushdown Automata
Ryoma Senda, Yoshiaki Takata, Hiroyuki Seki
Register pushdown automata (RPDA) is an extension of classical pushdown automata to handle data values in a restricted way. RPDA attracts attention as a model of a query language f…