標題: Titlebook: Automata, Languages, and Programming; 41st International C Javier Esparza,Pierre Fraigniaud,Elias Koutsoupias Conference proceedings 2014 S [打印本頁] 作者: autoantibodies 時間: 2025-3-21 16:59
書目名稱Automata, Languages, and Programming影響因子(影響力)
書目名稱Automata, Languages, and Programming影響因子(影響力)學(xué)科排名
書目名稱Automata, Languages, and Programming網(wǎng)絡(luò)公開度
書目名稱Automata, Languages, and Programming網(wǎng)絡(luò)公開度學(xué)科排名
書目名稱Automata, Languages, and Programming被引頻次
書目名稱Automata, Languages, and Programming被引頻次學(xué)科排名
書目名稱Automata, Languages, and Programming年度引用
書目名稱Automata, Languages, and Programming年度引用學(xué)科排名
書目名稱Automata, Languages, and Programming讀者反饋
書目名稱Automata, Languages, and Programming讀者反饋學(xué)科排名
作者: 機警 時間: 2025-3-22 00:04
Handling Infinitely Branching WSTS) are naturally infinitely branching. Here we develop tools to handle infinitely branching WSTS by exploiting the crucial property that in the (ideal) completion of a well-quasi-ordered set, downward-closed sets are . unions of ideals. Then, using these tools, we derive decidability results and we d作者: Nefarious 時間: 2025-3-22 04:09 作者: NICE 時間: 2025-3-22 06:04
On the Decidability of MSO+U on Infinite Treesitrarily large sets. We conjecture that the MSO+U theory of the complete binary tree is undecidable. We prove a weaker statement: there is no algorithm which decides this theory and has a correctness proof in .. This is because the theory is undecidable, under a set-theoretic assumption consistent w作者: Coronary-Spasm 時間: 2025-3-22 12:01 作者: 通便 時間: 2025-3-22 16:58 作者: 支架 時間: 2025-3-22 17:23
On the Complexity of Temporal-Logic Path Checkinghe complexity of this task was recently shown to be in . [9]. In this paper, we present an . algorithm for ., a quantitative (or metric) extension of ., and give an . algorithm for ., the unary fragment of .. At the time of writing, . is the most expressive logic with an . path-checking algorithm, a作者: 疼死我了 時間: 2025-3-22 22:21 作者: 粘連 時間: 2025-3-23 04:23 作者: guardianship 時間: 2025-3-23 05:41
The Complexity of Ergodic Mean-payoff Games all states are visited infinitely often with probability 1. The algorithmic study of ergodic games was initiated in a seminal work of Hoffman and Karp in 1966, but all basic complexity questions have remained unresolved. Our main results for ergodic games are as follows: We establish (1) an optimal作者: modifier 時間: 2025-3-23 10:36
Toward a Structure Theory of Regular Infinitary Trace Languagesata – the class of deterministic Büchi automata being the most prominent among them. In this paper, we analyze the situation of regular languages of infinite Mazurkiewicz traces that model non-terminating, concurrent behaviors of distributed systems. Here, a corresponding classification is still mis作者: Incise 時間: 2025-3-23 13:52
Unary Pushdown Automata and Straight-Line Programst accept exactly the unary regular languages, but can be exponentially more succinct than finite-state automata. We complete the complexity landscape for udpda by showing that emptiness (and thus universality) is .-hard, equivalence and compressed membership problems are .-complete, and inclusion is作者: 現(xiàn)暈光 時間: 2025-3-23 20:43
Robustness against Power is PSpace-completee features a relaxed memory model providing very weak guarantees with respect to the ordering and atomicity of memory accesses..Due to these weaknesses, some programs that are correct under sequential consistency (SC) show undesirable effects when run under Power. We say that these programs are not 作者: hieroglyphic 時間: 2025-3-23 23:29 作者: 絕緣 時間: 2025-3-24 04:21 作者: 無效 時間: 2025-3-24 09:28
Coalgebraic Weak Bisimulation from Recursive Equations over Monadsus classes of systems that exhibit richer transition behaviour. Nearly all of the ensuing notions are instances of the more general notion of .. Weak bisimulation, however, has so far been much less amenable to a coalgebraic treatment. Here we attempt to close this gap by giving a coalgebraic treatm作者: Sinus-Node 時間: 2025-3-24 13:44 作者: JAMB 時間: 2025-3-24 14:56 作者: 暴露他抗議 時間: 2025-3-24 21:18
Annkatrin Heuschkel,Claudia Rahnfeldy-iteration algorithm by Hoffman and Karp; show that both our algorithm and the classical value-iteration algorithm can approximate the value in exponential time; and identify a subclass where the value-iteration algorithm is a FPTAS. We also show that the exact value can be expressed in the existen作者: 抵消 時間: 2025-3-25 01:55 作者: occurrence 時間: 2025-3-25 06:29 作者: nugatory 時間: 2025-3-25 10:33 作者: Atrium 時間: 2025-3-25 14:24 作者: 干旱 時間: 2025-3-25 18:24
The Complexity of Ergodic Mean-payoff Gamesy-iteration algorithm by Hoffman and Karp; show that both our algorithm and the classical value-iteration algorithm can approximate the value in exponential time; and identify a subclass where the value-iteration algorithm is a FPTAS. We also show that the exact value can be expressed in the existen作者: 經(jīng)典 時間: 2025-3-25 23:42
Unary Pushdown Automata and Straight-Line Programsin logarithmic space into a udpda, and this forms the basis for our lower bound proofs. We show .-hardness of the ordered matching problem for SLPs, from which we derive .-hardness for inclusion. In addition, we complete the complexity landscape for unary nondeterministic pushdown automata by showin作者: transplantation 時間: 2025-3-26 03:53
Robustness against Power is PSpace-completelic happens-before relation there is one in a certain normal form. Finally, we reduce the existence of such a normal-form computation to a language emptiness problem. Altogether, this yields a PS. algorithm for checking robustness against Power. We complement it by a matching lower bound to show PS.作者: 斜坡 時間: 2025-3-26 04:43
Computability in Anonymous Networks: Revocable vs. Irrecovable Outputsutability which we apply to the classic/characteristic problems. Among our findings is the observation that the three classes are characterized by the three pillars of distributed computing, namely, local symmetry breaking, coordination, and leader election.作者: GENUS 時間: 2025-3-26 11:57 作者: 浸軟 時間: 2025-3-26 15:22
Conference proceedings 2014ogramming, ICALP 2014, held in Copenhagen, Denmark, in July 2014. The total of 136 revised full papers presented together with 4 invited talks were carefully reviewed and selected from 484 submissions. The papers are organized in three tracks focussing on Algorithms, Complexity, and Games, Logic, Se作者: Individual 時間: 2025-3-26 18:06
0302-9743 ges and Programming, ICALP 2014, held in Copenhagen, Denmark, in July 2014. The total of 136 revised full papers presented together with 4 invited talks were carefully reviewed and selected from 484 submissions. The papers are organized in three tracks focussing on Algorithms, Complexity, and Games,作者: 嚴重傷害 時間: 2025-3-26 23:11
Gewissensinterpretationen im Alltagtring function. With such semantics, the model admits a machine-independent characterisation, Angluin-style learning in polynomial time, as well as effective characterisations of natural subclasses such as one-way transducers or first-order definable transducers.作者: cornucopia 時間: 2025-3-27 05:04
Gewissensmanagement in Organisationenm which decides this theory and has a correctness proof in .. This is because the theory is undecidable, under a set-theoretic assumption consistent with ., namely that there exists of projective well-ordering of 2. of type?... We use Shelah’s undecidability proof of the MSO theory of the real numbers.作者: STEER 時間: 2025-3-27 06:18
https://doi.org/10.1007/978-3-322-90070-8ng to inclusion between sets of finite traces, based on approximation. We obtain inclusion of tree languages as a sound and complete method to show semantic subtyping of recursive types with basic types, product and union, interpreted coinductively.作者: 馬籠頭 時間: 2025-3-27 12:57
Gewohnheitsrecht und r?misches Rechtidable. We go one step further in this article by giving a full characterization of the sets of Turing degrees of limit sets of cellular automata: they are the same as the sets of Turing degrees of effectively closed sets containing a computable point.作者: GRAIN 時間: 2025-3-27 14:19
Transducers with Origin Informationtring function. With such semantics, the model admits a machine-independent characterisation, Angluin-style learning in polynomial time, as well as effective characterisations of natural subclasses such as one-way transducers or first-order definable transducers.作者: Antarctic 時間: 2025-3-27 20:15 作者: 憤怒事實 時間: 2025-3-28 00:59 作者: Vulnerable 時間: 2025-3-28 04:18 作者: 一回合 時間: 2025-3-28 09:35
https://doi.org/10.1007/978-3-531-91667-5e examples to show that this need not hold. In proving these results we generalize the notion of uniform minimality to direct products of automata. We also establish a non-trivial connection between complexity of boolean operations and group theory.作者: Cocker 時間: 2025-3-28 14:14
Von der Kolonie zur Freien Gemeinde,ularising the reasoning about concurrent programs using parameterised libraries and confirm the appropriateness of the proposed definitions. We illustrate the applicability of our results by proving the correctness of a parameterised library implementing flat combining.作者: 售穴 時間: 2025-3-28 15:48 作者: Vasoconstrictor 時間: 2025-3-28 21:21 作者: DALLY 時間: 2025-3-29 02:34
Seen, Flüsse, Grundwasser und Meere that high performance counters and stacks designed to satisfy quiescent consistency continue to satisfy QQC. The precise assumptions under which QQC holds provides fresh insight on these structures. To demonstrate the robustness of QQC, we provide three natural characterizations and prove compositionality.作者: corporate 時間: 2025-3-29 05:16
Symmetric Groups and Quotient Complexity of Boolean Operationse examples to show that this need not hold. In proving these results we generalize the notion of uniform minimality to direct products of automata. We also establish a non-trivial connection between complexity of boolean operations and group theory.作者: Expediency 時間: 2025-3-29 07:31
Parameterised Linearisabilityularising the reasoning about concurrent programs using parameterised libraries and confirm the appropriateness of the proposed definitions. We illustrate the applicability of our results by proving the correctness of a parameterised library implementing flat combining.作者: Misgiving 時間: 2025-3-29 15:00
Games with a Weak Adversaryperfect observation, memory of size non-elementary is necessary in general for reachability objectives, and the problem is decidable for safety and reachability objectives. From our results we derive new complexity results for partial-observation stochastic games.作者: 染色體 時間: 2025-3-29 15:54
A Nivat Theorem for Weighted Timed Automata and Weighted Relative Distance Logicative distance logic. Since the proof of our Nivat theorem is constructive, the translation process from logic to automata and vice versa is also constructive. This leads to decidability results for weighted relative distance logic.作者: 新星 時間: 2025-3-29 21:47 作者: Intuitive 時間: 2025-3-30 01:50 作者: oxidant 時間: 2025-3-30 07:47
0302-9743 ks were carefully reviewed and selected from 484 submissions. The papers are organized in three tracks focussing on Algorithms, Complexity, and Games, Logic, Semantics, Automata, and Theory of Programming, Foundations of Networked Computation.978-3-662-43950-0978-3-662-43951-7Series ISSN 0302-9743 Series E-ISSN 1611-3349 作者: 代理人 時間: 2025-3-30 12:05 作者: 祝賀 時間: 2025-3-30 13:16
https://doi.org/10.1007/978-3-642-92267-1sing. We introduce the model of “synchronization-aware asynchronous automata”, which allows us to initiate a classification of regular infinitary trace languages in a form that is in nice correspondence to the case of .-regular word languages.作者: 調(diào)色板 時間: 2025-3-30 17:03 作者: CLAN 時間: 2025-3-30 21:00 作者: 自負的人 時間: 2025-3-31 02:55 作者: 燦爛 時間: 2025-3-31 08:11 作者: 不要不誠實 時間: 2025-3-31 09:17
Lecture Notes in Computer Sciencehttp://image.papertrans.cn/b/image/166238.jpg作者: HATCH 時間: 2025-3-31 17:10
https://doi.org/10.1007/978-3-662-43951-7approximation algorithms; cellular automata; computational complexity; cryptography; dynamic programming作者: FID 時間: 2025-3-31 20:28 作者: insincerity 時間: 2025-4-1 01:01 作者: lattice 時間: 2025-4-1 02:29 作者: 阻撓 時間: 2025-4-1 10:02
Weak , with Path Quantifiers over Infinite TreesThis paper shows that over infinite trees, satisfiability is decidable for weak monadic second-order logic extended by the unbounding quantifier . and quantification over infinite paths. The proof is by reduction to emptiness for a certain automaton model, while emptiness for the automaton model is decided using profinite trees.作者: Confidential 時間: 2025-4-1 12:59
Piecewise Boolean Algebras and Their DomainsWe characterise piecewise Boolean domains, that is, those domains that arise as Boolean subalgebras of a piecewise Boolean algebra. This leads to equivalent descriptions of the category of piecewise Boolean algebras: either as piecewise Boolean domains equipped with an orientation, or as full structure sheaves on piecewise Boolean domains.作者: LEERY 時間: 2025-4-1 18:23
