標(biāo)題: Titlebook: Computer Science - Theory and Applications; 8th International Co Andrei A. Bulatov,Arseny M. Shur Conference proceedings 2013 Springer-Verl [打印本頁] 作者: 要旨 時間: 2025-3-21 17:39
書目名稱Computer Science - Theory and Applications影響因子(影響力)
書目名稱Computer Science - Theory and Applications影響因子(影響力)學(xué)科排名
書目名稱Computer Science - Theory and Applications網(wǎng)絡(luò)公開度
書目名稱Computer Science - Theory and Applications網(wǎng)絡(luò)公開度學(xué)科排名
書目名稱Computer Science - Theory and Applications被引頻次
書目名稱Computer Science - Theory and Applications被引頻次學(xué)科排名
書目名稱Computer Science - Theory and Applications年度引用
書目名稱Computer Science - Theory and Applications年度引用學(xué)科排名
書目名稱Computer Science - Theory and Applications讀者反饋
書目名稱Computer Science - Theory and Applications讀者反饋學(xué)科排名
作者: 生銹 時間: 2025-3-21 23:53 作者: Esophagitis 時間: 2025-3-22 02:42
Alphabetic Minimax Trees in Linear Timed with those weights when read from left to right minimizing the maximum value of .. plus the depth of the corresponding leaf. This improves the previously known .(.log.) time solutions?[3,10,12]. Assuming that the integer and the fractional part of each weight is given separately, our solution work作者: MINT 時間: 2025-3-22 06:45
Walking on Data Wordsdel of automaton walking on data words, called Data Walking Automaton, and study its closure properties, expressiveness, and the complexity of paradigmatic problems. We prove that deterministic DWA are strictly included in non-deterministic DWA, that the former subclass is closed under all boolean o作者: Mosaic 時間: 2025-3-22 09:15 作者: intuition 時間: 2025-3-22 13:18
Random Generation of Deterministic Acyclic Automata Using the Recursive Methodthod. The generator has a preprocessing that requires . arithmetic operations, and, once it is done, can generate acyclic automata using . arithmetic operations for each sample. We also propose a lazy version of the algorithm that takes advantage of the typical shape of random acyclic automata to re作者: intuition 時間: 2025-3-22 18:47
Boolean Language Operations on Nondeterministic Automata with a Pushdown of Constant Heightnential simulation and prove that the exponential blow-up is necessary. For ., instead, we provide a linear trade-off while, for ., we show a double-exponential simulation and prove a single-exponential lower bound.作者: goodwill 時間: 2025-3-22 22:32
Exponential Lower Bounds for Refuting Random Formulas Using Ordered Binary Decision Diagramsower bounds for a strong variant of this system using feasible interpolation [14], and Tveretina et al. proved exponential lower bounds for restricted versions of this system for refuting formulas derived from the Pigeonhole Principle [20]. In this paper we prove the first lower bounds for refuting 作者: 正常 時間: 2025-3-23 04:19 作者: 聲音刺耳 時間: 2025-3-23 06:16 作者: 笨重 時間: 2025-3-23 10:42
Information Lower Bounds via Self-reducibility: Gap Hamming Distance (GHD) and Inner Product (IP). In our first result we affirm the conjecture that the information cost of GHD : is linear even under the .distribution, which strengthens the Ω(.) bound recently shown by [15], and answering an open problem from [10]. In our second result we prove作者: overshadow 時間: 2025-3-23 16:34
On the Encoding Invariance of Polynomial Time Computable Distribution Ensemblesness, which is more convenient than previously used polynomial time computable distributions (PComp). The notion of a PISamp distribution is encoding invariant, while PComp distributions are not, if one-way permutations exist. Here we prove that PComp distributions are not encoding invariant under a作者: Left-Atrium 時間: 2025-3-23 20:53 作者: moratorium 時間: 2025-3-23 23:40
Amortized Communication Complexity of an Equality Predicate complexity of this problem is equal to .(.); the computational complexity of the proposed protocol is polynomial in the size of inputs. Our protocol improves the result achieved in 1991 by Feder et al. Our construction is based on two techniques: Nisan’s pseudorandom generator (1992, Nisan) and Smi作者: 是突襲 時間: 2025-3-24 05:26
Careful Synchronization of Partial Automata with Restricted Alphabetse finite automata. We obtain a lower bound for the length of the shortest carefully synchronizing words of an automaton with a fixed number of states and a fixed number of letters. In particular, we consider this bound for automata over a binary alphabet. Our results improve previously known bounds.作者: forthy 時間: 2025-3-24 07:59 作者: 1FAWN 時間: 2025-3-24 13:37 作者: FLINT 時間: 2025-3-24 18:38
Conference proceedings 2013013. The 29 full papers presented in this volume were carefully reviewed and selected from 52 submissions. In addition the book contains 8 invited lectures. The papers are organized in topical sections on: algorithms; automata; logic and proof complexity; complexity; words and languages; and logic and automata.作者: Infirm 時間: 2025-3-24 20:22 作者: 培養(yǎng) 時間: 2025-3-24 23:56
Lecture Notes in Computer Sciencehttp://image.papertrans.cn/c/image/233827.jpg作者: occult 時間: 2025-3-25 03:50
The Chinese Education Policy LandscapeThe Local Lemma of Lovász has affected multiple sciences. We survey its impact on mathematics, computer science and statistical physics.作者: 喚醒 時間: 2025-3-25 08:55
Lucille Lok-Sun Ngan,Chan Kwok-bunIn this talk I will report on some recent results concerning decidability and enumeration for properties of automatic sequences. This is work with Jean-Paul Allouche, émilie Charlier, Narad Rampersad, Dane Henshall, Luke Schaeffer, Eric Rowland, Daniel Go?, and Hamoon Mousavi.作者: FACT 時間: 2025-3-25 12:39
,Silence, Script, and “New Understandings”,This paper gives a short introduction to order-invariant first-order logic and arb-invariant first-order logic. We present separating examples demonstrating the expressive power, as well as tools for proving certain expressive weaknesses of these logics.作者: 平淡而無味 時間: 2025-3-25 17:50
The Chinese Language in European TextsWe provide separations between the parameterized versions of Res(1) (Resolution) and Res(2). Using a different set of parameterized contradictions, we also separate the parameterized versions of Res.(1) (tree-Resolution) and Res.(2).作者: AFFIX 時間: 2025-3-25 22:13
The Chinese Language in European TextsWe outline two plausible approaches to improving the miserable state of affairs regarding lower bounds against probabilistic polynomial time (namely, the class .作者: 支架 時間: 2025-3-26 01:07
The Lovász Local Lemma – A SurveyThe Local Lemma of Lovász has affected multiple sciences. We survey its impact on mathematics, computer science and statistical physics.作者: Mosaic 時間: 2025-3-26 05:08
Decidability and Enumeration for Automatic Sequences: A SurveyIn this talk I will report on some recent results concerning decidability and enumeration for properties of automatic sequences. This is work with Jean-Paul Allouche, émilie Charlier, Narad Rampersad, Dane Henshall, Luke Schaeffer, Eric Rowland, Daniel Go?, and Hamoon Mousavi.作者: 濃縮 時間: 2025-3-26 11:22 作者: 擁護(hù)者 時間: 2025-3-26 15:39
Parameterized Resolution with Bounded ConjunctionWe provide separations between the parameterized versions of Res(1) (Resolution) and Res(2). Using a different set of parameterized contradictions, we also separate the parameterized versions of Res.(1) (tree-Resolution) and Res.(2).作者: 產(chǎn)生 時間: 2025-3-26 18:17 作者: debase 時間: 2025-3-26 23:55 作者: 凹處 時間: 2025-3-27 04:10
https://doi.org/10.1057/9781137339096retical bounds for the algorithm. Furthermore, we introduce some modifications of QuickHeapsort, both in-place and using . extra bits. We show that on every input the expected number of comparisons is . (in-place) respectively . (always .). Both estimates improve the previously known best results. (作者: Ligament 時間: 2025-3-27 07:09
Constructing and Performing Chineseness,d with those weights when read from left to right minimizing the maximum value of .. plus the depth of the corresponding leaf. This improves the previously known .(.log.) time solutions?[3,10,12]. Assuming that the integer and the fractional part of each weight is given separately, our solution work作者: Contend 時間: 2025-3-27 11:43
The Chinese Health System in Transitiondel of automaton walking on data words, called Data Walking Automaton, and study its closure properties, expressiveness, and the complexity of paradigmatic problems. We prove that deterministic DWA are strictly included in non-deterministic DWA, that the former subclass is closed under all boolean o作者: 同音 時間: 2025-3-27 14:16
China’s Healthcare Policy from 1949 to 2008e finite automata. We obtain a lower bound for the length of the shortest carefully synchronizing words of an automaton with a fixed number of states and a fixed number of letters. In particular, we consider this bound for automata over a binary alphabet. Our results improve previously known bounds.作者: progestogen 時間: 2025-3-27 18:00 作者: 圖畫文字 時間: 2025-3-28 00:19 作者: 瑪瑙 時間: 2025-3-28 02:42
,Silence, Script, and “New Understandings”,ower bounds for a strong variant of this system using feasible interpolation [14], and Tveretina et al. proved exponential lower bounds for restricted versions of this system for refuting formulas derived from the Pigeonhole Principle [20]. In this paper we prove the first lower bounds for refuting 作者: Lobotomy 時間: 2025-3-28 07:42 作者: 山頂可休息 時間: 2025-3-28 12:29
https://doi.org/10.1057/978-1-137-50291-9 an expansion of a graph is a good characterization of the resolution complexity of Tseitin formulas. We extend the method of Ben-Sasson and Wigderson of proving lower bounds for the size of resolution proofs to constraint satisfaction problems under an arbitrary finite alphabet. For Tseitin formula作者: TAIN 時間: 2025-3-28 15:25 作者: hedonic 時間: 2025-3-28 19:23
https://doi.org/10.1007/978-981-10-3915-7ness, which is more convenient than previously used polynomial time computable distributions (PComp). The notion of a PISamp distribution is encoding invariant, while PComp distributions are not, if one-way permutations exist. Here we prove that PComp distributions are not encoding invariant under a作者: 不能妥協(xié) 時間: 2025-3-28 23:04
https://doi.org/10.1007/978-981-10-3915-7me decision algorithm . for SAT there is a polynomial time samplable distribution such that . errs with probability at least 1/6???. on a random formula chosen with respect to that distribution. A challenging problem is to increase the error probability to the maximal possible 1/2???. (the random gu作者: 痛苦一下 時間: 2025-3-29 05:24 作者: 牌帶來 時間: 2025-3-29 10:07
Computer Science - Theory and Applications978-3-642-38536-0Series ISSN 0302-9743 Series E-ISSN 1611-3349 作者: Clinch 時間: 2025-3-29 15:17
China’s Healthcare Policy from 1949 to 2008e finite automata. We obtain a lower bound for the length of the shortest carefully synchronizing words of an automaton with a fixed number of states and a fixed number of letters. In particular, we consider this bound for automata over a binary alphabet. Our results improve previously known bounds.作者: auxiliary 時間: 2025-3-29 18:26 作者: 織物 時間: 2025-3-29 19:57 作者: 生氣地 時間: 2025-3-29 23:54
https://doi.org/10.1007/978-3-642-38536-0computational complexity; decidability; formal methods; multi-weighted automata; prefix-free languages; a作者: essential-fats 時間: 2025-3-30 06:02
978-3-642-38535-3Springer-Verlag Berlin Heidelberg 2013作者: Radiculopathy 時間: 2025-3-30 09:44 作者: acrobat 時間: 2025-3-30 16:25
Graph Expansion, Tseitin Formulas and Resolution Proofs for CSP lower bounds. Let .?=?〈.,. 〉 be the dependency graph of the CSP, vertices of . correspond to constraints; two constraints are connected by an edge for every common variable. We prove that the tree-like resolution complexity of the CSP is at most . for some subgraph . of ..作者: FLORA 時間: 2025-3-30 19:26 作者: HERTZ 時間: 2025-3-30 22:31
,Silence, Script, and “New Understandings”,n complexity lower bounds a two-way connection. Whereas numerous results in the past [13,2,3] used information complexity techniques to derive new communication complexity lower bounds, we explore a generic way in which communication complexity lower bounds imply information complexity lower bounds ..作者: 哪有黃油 時間: 2025-3-31 01:03
Exponential Lower Bounds for Refuting Random Formulas Using Ordered Binary Decision Diagramser in which the clauses of the input formula must be processed. We show that for some constant .?>?0, with high probability an OBDD* refutation of an unsatisfiable random 3-CNF formula must be of size at least 2., and an OBDD+ refutation of an unsatisfiable random 3-XOR formula must be of size at least 2..作者: NUDGE 時間: 2025-3-31 06:35
Information Lower Bounds via Self-reducibilityn complexity lower bounds a two-way connection. Whereas numerous results in the past [13,2,3] used information complexity techniques to derive new communication complexity lower bounds, we explore a generic way in which communication complexity lower bounds imply information complexity lower bounds ..作者: Madrigal 時間: 2025-3-31 10:38 作者: Harridan 時間: 2025-3-31 16:11 作者: lipids 時間: 2025-3-31 18:55
The Chinese Health System in Transitionoperations for each sample. We also propose a lazy version of the algorithm that takes advantage of the typical shape of random acyclic automata to reduce experimentally the preprocessing. Using this algorithm, we provide some statistics on acyclic automata with up to 1000 states.作者: thyroid-hormone 時間: 2025-3-31 21:46 作者: Ablation 時間: 2025-4-1 05:08 作者: 雕鏤 時間: 2025-4-1 09:25 作者: Exhilarate 時間: 2025-4-1 14:09 作者: chastise 時間: 2025-4-1 16:02
Random Generation of Deterministic Acyclic Automata Using the Recursive Methodoperations for each sample. We also propose a lazy version of the algorithm that takes advantage of the typical shape of random acyclic automata to reduce experimentally the preprocessing. Using this algorithm, we provide some statistics on acyclic automata with up to 1000 states.作者: 編輯才信任 時間: 2025-4-1 22:02
