Fuzzy Pushdown Termination Games

The computational study on finite/infinite-state systems, probabilistic systems, and finite-state fuzzy systems, has received much attention recently. In contrast, there are very few results for algorithmic analysis of infinite-state fuzzy systems. In this paper, we introduce fuzzy pushdown terminat...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on fuzzy systems 2019-04, Vol.27 (4), p.760-774
Main Authors: Pan, Haiyu, Song, Fu, Cao, Yongzhi, Qian, Junyan
Format: Article
Language:English
Subjects:
Algorithms
Analytical models
Automata
Computational modeling
Fuzzy automata
Fuzzy sets
Fuzzy systems
Games
Probabilistic logic
pushdown automata (PDAs)
pushdown game
reachability problem
triangular norm
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The computational study on finite/infinite-state systems, probabilistic systems, and finite-state fuzzy systems, has received much attention recently. In contrast, there are very few results for algorithmic analysis of infinite-state fuzzy systems. In this paper, we introduce fuzzy pushdown termination games (FPDTGs), which are an extension of fuzzy pushdown automata with a game feature and can serve as a formal model of infinite-state fuzzy systems. We investigate some computational issues of the games under termination objectives for two players: the goal of player-1 is to maximize the truth value of eventually terminating at some given configurations with the empty stack, while player-2 aims at the opposite. Some interesting results are obtained. For example, we show that both players have optimal memoryless strategies and the same value. The problem of computing the value can be solved in exponential time when the triangular norm is chosen as the minimum one. Furthermore, we present efficient algorithms for computing the values of two special subclasses of FPDTGs. The potential for practical use of our model is demonstrated by a case study on a manufacturing system.
ISSN:1063-6706
1941-0034
DOI:10.1109/TFUZZ.2018.2869127