检索结果-内蒙古大学图书馆

Exploiting symmetries of high-level Petri games in distributed synthesis

IT-INFORMATION TECHNOLOGY 2021年第5-6期63卷 321-331页

作者： Wurdemann, Nick Carl von Ossietzky Univ Oldenburg Dept Comp Sci D-26129 Oldenburg Germany

distributed synthesis is the problem of automatically generating correct controllers for individual agents in a distributed system. Petri games model this problem by a game between two teams of players on a Petri net structure. Under some restrictions, Petri games can be solved by a reduction to a two player game. The concept of symmetries in Petri nets is closely related to high-level representations of Petri games. Applying symmetries to the states in the two-player game results in a significant state space reduction. We give an overview about (high-level) Petri games and the application of symmetries in this setting. We present ongoing work aiming to concisely describe solutions of Petri games by a high-level representation.

关键词： distributed synthesis Symmetries High-Level Petri Nets Petri Games

来源：评论

学校读者我要写书评

暂无评论

distributed synthesis for parameterized temporal logics

引用

INFORMATION AND COMPUTATION 2018年第Part2期262卷 311-328页

作者： Jacobs, Swen Tentrup, Leander Zimmermann, Martin Saarland Univ React Syst Grp D-66123 Saarbrucken Germany

We consider the synthesis of distributed implementations for specifications in parameterized temporal logics such as PROMPT-LTL, which extends LTL by temporal operators equipped with parameters that bound their scope. For single process synthesis, it is well-established that such parametric extensions do not increase worst-case complexities. For synchronous distributed systems, we show that, despite being more powerful, the realizability problem for PROMPT-LTL is not harder than its LTL counter part. For asynchronous systems, we have to express scheduling assumptions and therefore consider an assume-guarantee synthesis problem. As asynchronous distributed synthesis is already undecidable for LTL, we give a semi-decision procedure for the PROMPT-LTL assume-guarantee synthesis problem based on bounded synthesis. Finally, we show that our results extend to the stronger logics PLTL and PLDL. (C) 2018 Elsevier Inc. All rights reserved.

关键词： distributed synthesis distributed realizability Incomplete information Parametric linear temporal logic Parametric linear dynamic logic

来源：评论

学校读者我要写书评

暂无评论

distributed synthesis is simply undecidable

引用

INFORMATION PROCESSING LETTERS 2014年第4期114卷 203-207页

作者： Schewe, Sven Univ Liverpool Liverpool L69 3BX Merseyside England

The distributed synthesis problem of safety and reachability languages is known to be undecidable. In this article, we establish that this is the case for very simple languages, namely for safety and reachability specifications in the intersection of LTL and ACTL. (C) 2013 The Author. Published by Elsevier B.V. All rights reserved.

关键词： Formal methods distributed synthesis Undecidability Temporal logic

来源：评论

学校读者我要写书评

暂无评论

Most General Winning Secure Equilibria synthesis in Graph Games 30th

Most General Winning Secure Equilibria Synthesis in Graph Ga...

引用

30th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS) Held as Part of the 27th European Joint Conferences on Theory and Practice of Software (ETAPS)

作者： Nayak, Satya Prakash Schmuck, Anne-Kathrin Max Planck Inst Software Syst Kaiserslautern Germany

ISBN: (纸本)9783031572555;9783031572562

This paper considers the problem of co-synthesis in k-player games over a finite graph where each player has an individual omega-regular specification phi(i). In this context, a secure equilibrium (SE) is a Nash equilibrium w.r.t. the lexicographically ordered objectives of each player to first satisfy their own specification, and second, to falsify other players' specifications. A winning secure equilibrium (WSE) is an SE strategy profile (pi(i)) i(is an element of)[1;k] that ensures the specification. phi=Lambda(i is an element of)[1;k]phi(i) if no player deviates from their strategy pi(i). distributed implementations generated from a WSE make components act rationally by ensuring that a deviation from the WSE strategy profile is immediately punished by a retaliating strategy that makes the involved players lose. In this paper, we move from deviation punishment in WSE-based implementations to a distributed, assume-guarantee based realization of WSE. This shift is obtained by generalizing WSE from strategy profiles to specification profiles (phi(i)) i(is an element of)[1;k] with Lambda(i is an element of)[1;k] phi(i) = phi, which we call most general winning secure equilibria (GWSE). Such GWSE have the property that each player can individually pick a strategy pi(i) winning for phi(i) (against all other players) and all resulting strategy profiles (pi(i))i(is an element of)[1;k] are guaranteed to be a WSE. The obtained flexibility in players' strategy choices can be utilized for robustness and adaptability of local implementations. Concretely, our contribution is three-fold: (1) we formalize GWSE for k-player games over finite graphs, where each player has an.-regular specification phi(i);(2) we devise an iterative semi-algorithm for GWSE synthesis in such games, and (3) obtain an exponential-time algorithm for GWSE synthesis with parity specifications phi(i).

关键词： distributed synthesis Parity Games Secure Equilibria Assume-Guarantee Contracts

来源：评论

学校读者我要写书评

暂无评论

Strategy Logic with Imperfect Information

引用

ACM TRANSACTIONS ON COMPUTATIONAL LOGIC 2021年第1期22卷 1–51页

作者： Berthon, Raphael Maubert, Bastien Murano, Aniello Rubin, Sasha Vardi, Moshe Y. Univ Libre Bruxelles Comp Sci Dept Bat NOCP 212Campus PlaineBlvd Triomphe B-1050 Ixelles Belgium Univ Antwerp Antwerp Belgium Univ Napoli Federico II Dipartimento Ingn Elettr & Tecnol Informaz Via Claudio 21 I-80125 Naples Italy Univ Sydney Sch Comp Sci Recept Bldg J121 Cleveland St Darlington NSW 2008 Australia Rice Univ Dept Comp Sci Mail Stop 1326100 S Main St Houston TX 77005 USA

We introduce an extension of Strategy Logic for the imperfect-information setting, called SLii and study its model-checking problem. As this logic naturally captures multi-player games with imperfect information, this problem is undecidable;but we introduce a syntactical class of "hierarchical instances" for which, intuitively, as one goes down the syntactic tree of the formula, strategy quantifications are concerned with finer observations of the model, and we prove that model-checking SLii restricted to hierarchical instances is decidable. This result. because it allows for complex patterns of existential and universal quantification on strategies, greatly generalises the decidability of distributed synthesis for systems with hierarchical information. It allows us to easily derive new decidability results concerning strategic problems under imperfect information such as the existence of Nash equilibria or rational synthesis. To establish this result, we go through an intermediary, "low-level" logic much more adapted to automata techniques. QCTL* is an extension of CTL* with second-order quantification over atomic propositions that has been used to study strategic logics with perfect information. We extend it to the imperfect information setting by parameterising second-order quantifiers with observations. The simple syntax of the resulting logic, QCTL(ii)*, allows us to provide a conceptually neat reduction of SLii to QCTL(ii)* that separates concerns, allowing one to forget about strategies and players and focus solely on second-order quantification. While the model-checking problem of QCTL(ii)* is, in general, undecidable, we identify a syntactic fragment of hierarchical formulas and prove, using an automata-theoretic approach, that it is decidable.

关键词： Strategic reasoning imperfect information perfect recall distributed synthesis hierarchical information Nash equilibria rational synthesis

来源：评论

学校读者我要写书评

暂无评论

Handbook of Automata Theory

引用

2021年

作者： Jean-Éric Pin

ISBN: (数字)9783985475063

ISBN: (纸本)9783985470068

Automata theory is a subject of study at the crossroads of mathematics, theoretical computer science, and applications. In its core it deals with abstract models of systems whose behaviour is based on transitions between states, and it develops methods for the description, classification, analysis, and design of such systems. The Handbook of Automata Theory gives a comprehensive overview of current research in automata theory, and is aimed at a broad readership of researchers and graduate students in mathematics and computer science. Volume I is divided into three parts. The first part presents various types of automata: automata on words, on infinite words, on finite and infinite trees, weighted and maxplus automata, transducers, and two-dimensional models. Complexity aspects are discussed in the second part. Algebraic and topological aspects of automata theory are covered in the third part. Volume II consists of two parts. The first part is dedicated to applications of automata in mathematics: group theory, number theory, symbolic dynamics, logic, and real functions. The second part presents a series of further applications of automata theory such as message-passing systems, symbolic methods, synthesis, timed automata, verification of higher-order programs, analysis of probabilistic processes, natural language processing, formal verification of programs and quantum computing. The two volumes comprise a total of thirty-nine chapters, with extensive references and individual tables of contents for each one, as well as a detailed subject index.

关键词： finite automata Hopcroft's algorithm regular languages regular expressions finite transducers weighted automata automata on infinite words automata on trees picture languages algorithmic learning descriptional complexity Boolean circuits synchronizing automata road colouring problem varieties of languages profinite topology descriptive set theory equational theories language equations forest algebras free groups Stallings automata automatic groups self-similar groups automatic sequences numeration systems Cobham's theorem symbolic dynamics synchronous automata finite model theory fractal image generation communicating automata model-checking Church's problem distributed synthesis timed automata recursion schemes Markov decision processes infinite-state systems natural language processing temporal logic branching time logic quantum finite automata

来源：评论

学校读者我要写书评

暂无评论

On distributed and Parameterized Supervisor synthesis Problems

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2016年第3期61卷 777-782页

作者： Lin, Liyong Stefanescu, Alin Su, Rong Nanyang Technol Univ Sch Elect & Elect Engn Singapore 639798 Singapore Univ Bucharest Dept Comp Sci Bucharest 010014 Romania

It is shown that the problem whether an arbitrary regular language has a non-empty decomposable sublanguage with respect to a fixed distribution is decidable if and only if the independence relation induced by the distribution is transitive. A sufficient condition on the distributed control architecture is then derived, under which there exist some fixed non-blocking local generators such that the distributed supervisor synthesis problem is undecidable. We also show that a natural formulation of the parameterized supervisor synthesis problem is undecidable for a fixed non-blocking generator template, so long as the template alphabet has at least two private events and one global event that are controllable. In particular, all the undecidability results are still valid even if star free specification languages are considered.

关键词： Discrete-event systems distributed synthesis parameterized synthesis supervisory control trace theory

来源：评论

学校读者我要写书评

暂无评论

Infinite games with finite knowledge gaps

引用

INFORMATION AND COMPUTATION 2017年第Part2期254卷 217-237页

作者： Berwanger, Dietmar Mathew, Anup Basil Univ Paris Saclay CNRS ENS Cachan LSV F-94235 Cachan France Inst Math Sci Madras 600113 Tamil Nadu India

Infinite games where several players seek to coordinate under imperfect information are deemed to be undecidable, unless the information is hierarchically ordered among the players. We identify a class of games for which joint winning strategies can be constructed effectively without restricting the direction of information flow. Instead, our condition requires that the players attain common knowledge about the actual state of the game over and over again along every play. We show that it is decidable whether a given game satisfies the condition, and prove tight complexity bounds for the strategy synthesis problem under co-regular winning conditions given by deterministic parity automata. (C) 2016 Elsevier Inc. All rights reserved.

关键词： Games on graphs Infinite games Imperfect information distributed synthesis Coordination

来源：评论

学校读者我要写书评

暂无评论

Time Optimal synthesis Based Upon Sequential Abstraction and Its Application to Cluster Tools

引用

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 2017年第2期14卷 772-784页

作者： Ware, Simon Su, Rong Nanyang Technol Univ Sch Elect & Elect Engn Singapore 639798 Singapore

The Ramadge-Wonham supervisory control paradigm has been shown effective in dealing with logic control. Nevertheless, time-related performance is always one of the major concerns in industry. Current methods for synthesizing time optimal supervisors are incapable of dealing with large discrete-event systems (DESs) with massive state spaces. This paper proposes an approach for finding a time optimal accepting trace for large DESs based upon sequential language projection, and pruning. The algorithms are tested on a linear cluster tool to show their effectiveness.

关键词： Discrete-event systems (DESs) distributed synthesis finite-state automata time optimal supervisory control

来源：评论

学校读者我要写书评

暂无评论

DETECTING UNREALIZABILITY OF distributed FAULT-TOLERANT SYSTEMS

引用

LOGICAL METHODS IN COMPUTER SCIENCE 2015年第3期11卷

作者： Finkbeiner, Bernd Tentrup, Leander Univ Saarland D-66123 Saarbrucken Germany

Writing formal specifications for distributed systems is difficult. Even simple consistency requirements often turn out to be unrealizable because of the complicated information flow in the distributed system: not all information is available in every component, and information transmitted from other components may arrive with a delay or not at all, especially in the presence of faults. The problem of checking the distributed realizability of a temporal specification is, in general, undecidable. Semi-algorithms for synthesis, such as bounded synthesis, are only useful in the positive case, where they construct an implementation for a realizable specification, but not in the negative case: if the specification is unrealizable, the search for the implementation never terminates. In this paper, we introduce counterexamples to distributed realizability and present a method for the detection of such counterexamples for specifications given in linear-time temporal logic (LTL). A counterexample consists of a set of paths, each representing a different sequence of inputs from the environment, such that, no matter how the components are implemented, the specification is violated on at least one of these paths. We present a method for finding such counterexamples both for the classic distributed realizability problem and for the fault-tolerant realizability problem. Our method considers, incrementally, larger and larger sets of paths until a counterexample is found. For safety specifications in weakly ordered architectures we obtain a decision procedure, while counterexamples for full LTL and arbitrary architectures may consist of infinitely many paths. Experimental results, obtained with a QBF-based prototype implementation, show that our method finds simple errors very quickly, and even problems with high combinatorial complexity, like the Byzantine Generals' Problem, are tractable.

关键词： distributed synthesis Fault-tolerance Coordination Logic

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：