標題: Titlebook: Automata, Languages, and Programming; 21st International C Serge Abiteboul,Eli Shamir Conference proceedings 1994 Springer-Verlag Berlin He [打印本頁] 作者: 決絕 時間: 2025-3-21 18:37
書目名稱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-21 22:10 作者: 記憶法 時間: 2025-3-22 03:51 作者: 態(tài)學(xué) 時間: 2025-3-22 08:32
Deciding properties of integral relational automata,RA). The general model checking problem for CTL. formulae over RA is shown ., the undecidability being observed already on the class of Restricted CTL formulae. The decidability result, however, is obtained for another substantial subset of the logic, called A-CTL.+, which includes all ”linear time”作者: 踉蹌 時間: 2025-3-22 09:29
On the cost of recomputing: tight bounds on pebbling with faults,xities were studied using the “pebbling game” model. We extend this model to the faulty case, where the content of memory cells may be erased. The model captures notions such as “check points” (keeping multiple copies of intermediate results), and “recovery” (partial recomputing in the case of failu作者: arthroplasty 時間: 2025-3-22 13:26 作者: cancellous-bone 時間: 2025-3-22 17:23
Complexity results for multi-pebble automata and their logics,erminism and concurrency. We investigate the succinctness of such machines, and the extent to which this succinctness carries over to make the reasoning problem in propositional dynamic logic (PDL) more difficult. The two main results establish that each additional pebble provides inherent exponenti作者: 微枝末節(jié) 時間: 2025-3-22 23:03
An analysis of the Core-ML language: Expressive power and type reconstruction, over atomic constants, and let as the only polymorphic construct. We present a synthesis of recent results which characterize this “toy” language‘s expressive power as well as its type reconstruction (or type inference) problem. More specifically: (1) Core-ML can express exactly the ELEMENTARY quer作者: IRATE 時間: 2025-3-23 01:32
Expressiveness of efficient semi-deterministic choice constructs,are no natural determinate-complete query languages known, more restrictive (the .) and more general (the .) notions of query were considered. Here, we show that the advantage of the second approach over the first is not so much in increased expressiveness, but in the ability of expressing queries m作者: CRAFT 時間: 2025-3-23 05:52
Tailoring recursion for complexity,s of global functions for a number of complexity classes for which such algebras have not been known, e.g. for the functions computable in nondeterministic logarithmic space, or in nondeterministic polynomial time. In addition, we present a functional analogue of first-order logic and give a new fun作者: CHIP 時間: 2025-3-23 12:29 作者: Neuralgia 時間: 2025-3-23 17:08
,On the complementation of Büchi asynchronous cellular automata,ynchronous cellular automata for finite traces, which has been open for several years. We use the subset automaton construction in order to extend Klarlund‘s progress measure technique of complementation to non-deterministic asynchronous cellular Büchi automata for infinite traces. Our automaton for作者: Compassionate 時間: 2025-3-23 18:15
Distribution and locality of concurrent systems, based on a set of distributed transition rules that record spatial information and on a notion of equivalence that discriminates according to which actions processes can perform and where these actions are performed. The new semantics is proven to coincide with the . of Boudol, Castellani, Hennessy作者: 甜得發(fā)膩 時間: 2025-3-23 23:05 作者: ambivalence 時間: 2025-3-24 03:49 作者: 機構(gòu) 時間: 2025-3-24 08:06
On the approximation of shortest common supersequences and longest common subsequences,hey have important applications in many areas including computational molecular biology (., sequence alignment), data compression, planning, text editing (. function in UNIX), etc. [1, 6, 7, 8, 10, 17, 19, 22, 23, 24, 26, 27]. The question of approximating SCS and LCS was raised 15 years ago in [19]作者: HIKE 時間: 2025-3-24 12:13 作者: CAB 時間: 2025-3-24 17:36 作者: Filibuster 時間: 2025-3-24 19:10 作者: MIR 時間: 2025-3-24 23:31
On the approximation of shortest common supersequences and longest common subsequences,t, if LCS has a polynomial-time approximation algorithm with performance ratio .., then . = .. Item (iii) is straightforward using recent breakthrough results in [3]. However, items (i) and (ii) require new ideas and techniques..In the second part of the paper, we introduce a new powerful method for作者: SHRIK 時間: 2025-3-25 04:14 作者: objection 時間: 2025-3-25 07:41
Steuermessbetrag, Zerlegung und Hebesatz,t, if LCS has a polynomial-time approximation algorithm with performance ratio .., then . = .. Item (iii) is straightforward using recent breakthrough results in [3]. However, items (i) and (ii) require new ideas and techniques..In the second part of the paper, we introduce a new powerful method for作者: 主動 時間: 2025-3-25 15:37 作者: Tremor 時間: 2025-3-25 17:52 作者: 直覺沒有 時間: 2025-3-25 22:09
Conference proceedings 1994in sections on theory of computation, automata and computation models, expressive power, automata and concurrency, pattern matching, data structures, computational complexity, logic and verification, formal languages, term rewriting, algorithms and communications, graph algorithms, randomized complexity, various algorithms.作者: heirloom 時間: 2025-3-26 00:11 作者: transplantation 時間: 2025-3-26 07:07
0302-9743 ructures, computational complexity, logic and verification, formal languages, term rewriting, algorithms and communications, graph algorithms, randomized complexity, various algorithms.978-3-540-58201-4978-3-540-48566-7Series ISSN 0302-9743 Series E-ISSN 1611-3349 作者: 支形吊燈 時間: 2025-3-26 10:04
Wasch- und Badeeinrichtungen; Abortelower bounds. But notice that the problem of proving nonlinear lower bounds on space-time tradeoffs on branching programs is ridiculously weak if compared to real problems such as “.?”. How difficult problems can we expect to encounter when solving those?作者: 漸強 時間: 2025-3-26 14:18 作者: indoctrinate 時間: 2025-3-26 19:29
Unexpected upper bounds on the complexity of some communication games,lower bounds. But notice that the problem of proving nonlinear lower bounds on space-time tradeoffs on branching programs is ridiculously weak if compared to real problems such as “.?”. How difficult problems can we expect to encounter when solving those?作者: 敲竹杠 時間: 2025-3-26 22:34 作者: 引起 時間: 2025-3-27 03:53
Die bauliche Anlage der Fabrik (Werkst?tten)n them), corresponding to the random-noise philosophy of Shannon. The third model is a nondeterministic version of the second one, where nondeterminism is defined on the fault probabilities. We express the computational power of the above models, and see that they are polynomially equivalent, in particular, P.=NP..作者: Concrete 時間: 2025-3-27 06:05 作者: Melanoma 時間: 2025-3-27 13:00
Steuermessbetrag, Zerlegung und Hebesatz,positionality results for both models. This pair of models, which generalize several existing models, is intended to comprise a general formalism for the verification of timed and untimed concurrent systems.作者: barium-study 時間: 2025-3-27 14:22
Steuermessbetrag, Zerlegung und Hebesatz,tion which allow us to conclude, without the explicit knowledge of that solution, the main result: searching for all occurrences of a random pattern in a random binary tree of joint size . and distributed accordingly to the bst probability model is . ln .) on the average.作者: 催眠 時間: 2025-3-27 21:33 作者: artifice 時間: 2025-3-27 23:27 作者: Directed 時間: 2025-3-28 05:03
Distribution and locality of concurrent systems,lence amenable to a mechanical treatment in the same vein as the classical bisimulation-based equivalences. Indeed, we propose a polynomial time algorithm for checking locality equivalence of processes.作者: 過度 時間: 2025-3-28 07:16
Liveness in timed and untimed systems,positionality results for both models. This pair of models, which generalize several existing models, is intended to comprise a general formalism for the verification of timed and untimed concurrent systems.作者: SHRIK 時間: 2025-3-28 12:51
Average-case analysis of pattern-matching in trees under the BST probability model,tion which allow us to conclude, without the explicit knowledge of that solution, the main result: searching for all occurrences of a random pattern in a random binary tree of joint size . and distributed accordingly to the bst probability model is . ln .) on the average.作者: inconceivable 時間: 2025-3-28 18:39 作者: LIEN 時間: 2025-3-28 20:19
0302-9743 salem in July 1994. ICALP is an annual conference sponsored by the European Association on Theoretical Computer Science (EATCS). The proceedings contains 48 refereed papers selected from 154 submissions and 4 invited papers. The papers cover the whole range of theoretical computer science; they are 作者: charisma 時間: 2025-3-29 02:58
Die bauliche Anlage der Fabrik (Werkst?tten)n regular expressions and contextfree grammars, or for defining outer measures on the space of .-words which are of some importance for the theory of fractals. These connections yield new formulae to determine the Hausdorff dimension of fractal sets (especially in Euclidean spaces) defined via regular expressions and contextfree grammars.作者: Psa617 時間: 2025-3-29 06:10 作者: Basal-Ganglia 時間: 2025-3-29 10:36 作者: monochromatic 時間: 2025-3-29 12:17 作者: Externalize 時間: 2025-3-29 19:28
Valuations and unambiguity of languages, with applications to fractal geometry,n regular expressions and contextfree grammars, or for defining outer measures on the space of .-words which are of some importance for the theory of fractals. These connections yield new formulae to determine the Hausdorff dimension of fractal sets (especially in Euclidean spaces) defined via regular expressions and contextfree grammars.作者: affinity 時間: 2025-3-29 19:53
On some relations between dynamical systems and transition systems,e reachability problem for such systems is undecidable for 3 dimensions. A decision procedure for 2-dimensional systems has been recently reported by Maler and Pnueli. On the other hand we show that some non-deterministic finite automata cannot be realized by any continuous dynamical system with less than 3 dimensions.作者: 油氈 時間: 2025-3-30 00:42 作者: 灰心喪氣 時間: 2025-3-30 04:40
Optimal parallel algorithms for Prefix Matching,rawn from an alphabet set of size polynomial in ., where . and .; it takes .(log .) time, .(..+..) space, and does . work, for any .>0. The second algorithm works for unbounded alphabet sets and takes .(log..(log log .).) time, .(m + n) space, and does . work. These are the first known work-optimal algorithms for this problem.作者: BANAL 時間: 2025-3-30 11:59 作者: 無效 時間: 2025-3-30 13:14
Wasch- und Badeeinrichtungen; AborteRA). The general model checking problem for CTL. formulae over RA is shown ., the undecidability being observed already on the class of Restricted CTL formulae. The decidability result, however, is obtained for another substantial subset of the logic, called A-CTL.+, which includes all ”linear time” formulae.作者: Endometrium 時間: 2025-3-30 18:20
Ergebnisse der bisherigen Forschung,erminism and concurrency. We investigate the succinctness of such machines, and the extent to which this succinctness carries over to make the reasoning problem in propositional dynamic logic (PDL) more difficult. The two main results establish that each additional pebble provides inherent exponential power on both fronts.作者: 弄皺 時間: 2025-3-30 21:26 作者: intimate 時間: 2025-3-31 02:19 作者: 媽媽不開心 時間: 2025-3-31 08:37 作者: 透明 時間: 2025-3-31 09:50
Maintaining spanning trees of small diameter,Given a graph . with . edges and . nodes, a spanning tree . of ., and an edge . that is being deleted from or inserted into ., we give efficient . algorithms to compute a possible swap for . that minimizes the diameter of the new spanning tree. This problem arises in high-speed networks, particularly in optical networks.作者: obviate 時間: 2025-3-31 14:33 作者: 絕種 時間: 2025-3-31 20:32 作者: 平庸的人或物 時間: 2025-4-1 00:21
Expressiveness of efficient semi-deterministic choice constructs,are no natural determinate-complete query languages known, more restrictive (the .) and more general (the .) notions of query were considered. Here, we show that the advantage of the second approach over the first is not so much in increased expressiveness, but in the ability of expressing queries more efficiently.作者: 儀式 時間: 2025-4-1 05:43 作者: deforestation 時間: 2025-4-1 08:15 作者: 可商量 時間: 2025-4-1 11:56
