Distributed synthesis for regular and contextfree specifications

被引：3

作者：

Fridman, Wladimir ^{[1
]}

Puchala, Bernd ^{[1
]}

机构：

[1] Rhein Westfal TH Aachen, Aachen, Germany

来源：

ACTA INFORMATICA | 2014年 / 51卷 / 3-4期

关键词：

Computers - Artificial intelligence;

D O I：

10.1007/s00236-014-0194-x

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We consider the distributed realizability problem for systems with regular and deterministic contextfree local specifications. We characterize exactly the architectures for which the realizability problem is decidable. This extends known results on local specifications in two directions. First, architectures with cycles are allowed instead of just acyclic ones and second, deterministic contextfree specifications are considered.

引用

页码：221 / 260

页数：40

共 20 条

[1] SOLVING SEQUENTIAL CONDITIONS BY FINITE-STATE STRATEGIES [J].

BUCHI, JR ;

LANDWEBER, LH .

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1969, 138 (APR) :295-+

[2]

CHURCH A, 1957, SUMMARIES SUMMER I S, V1, P3

[3] OMEGA-COMPUTATIONS ON DETERMINISTIC PUSHDOWN MACHINES [J].

COHEN, RS ;

GOLD, AY .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1978, 16 (03) :275-300

[4] Concurrent reachability games [J].

de Alfaro, L ;

Henzinger, TA ;

Kupferman, O .

39TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1998, :564-575

[5]

Finkbeiner B, 2005, IEEE S LOG, P321

[6] Topological properties of omega context-free languages [J].

Finkel, O .

THEORETICAL COMPUTER SCIENCE, 2001, 262 (1-2) :669-697

[7]

Fridman W., 2013, THESIS RWTH AACHEN U

[8]

Fridman W, 2011, LECT NOTES COMPUT SC, V6907, P532, DOI 10.1007/978-3-642-22993-0_48

[9] Pushdown specifications [J].

Kupferman, O ;

Piterman, N ;

Vardi, MY .

LOGIC FOR PROGRAMMING, ARTIFICIAL INTELLIGENCE, AND REASONING, 2002, 2514 :262-277

[10]

Kupferman O, 2001, IEEE S LOG, P389, DOI 10.1109/LICS.2001.932514

← 1 2 →