標(biāo)題: Titlebook: Descriptional Complexity of Formal Systems; 25th IFIP WG 1.02 In Henning Bordihn,Nicholas Tran,Gy?rgy Vaszil Conference proceedings 2023 IF [打印本頁] 作者: 落后的煤渣 時間: 2025-3-21 16:23
書目名稱Descriptional Complexity of Formal Systems影響因子(影響力)
書目名稱Descriptional Complexity of Formal Systems影響因子(影響力)學(xué)科排名
書目名稱Descriptional Complexity of Formal Systems網(wǎng)絡(luò)公開度
書目名稱Descriptional Complexity of Formal Systems網(wǎng)絡(luò)公開度學(xué)科排名
書目名稱Descriptional Complexity of Formal Systems被引頻次
書目名稱Descriptional Complexity of Formal Systems被引頻次學(xué)科排名
書目名稱Descriptional Complexity of Formal Systems年度引用
書目名稱Descriptional Complexity of Formal Systems年度引用學(xué)科排名
書目名稱Descriptional Complexity of Formal Systems讀者反饋
書目名稱Descriptional Complexity of Formal Systems讀者反饋學(xué)科排名
作者: 歡騰 時間: 2025-3-21 23:37 作者: 觀察 時間: 2025-3-22 04:28
https://doi.org/10.1007/978-94-007-6076-9em (a .-complete problem that is very convenient to prove the .-hardness of reversible games with pushing blocks). Direct use of this property introduces an explosion in the number of gadgets needed to show .-hardness, but we show how to bring that number from 32 down to only three in general, and d作者: 自然環(huán)境 時間: 2025-3-22 07:38
https://doi.org/10.1007/978-94-007-6076-9s in an accepting computation on . that uses least nondeterminism. The universal width of . on string . is the least number of parallel branches an accepting computation of . on . uses. The existential or universal width of . is said to be finite if it is bounded for all accepted strings. We show th作者: Coronary-Spasm 時間: 2025-3-22 11:06 作者: Expertise 時間: 2025-3-22 14:21 作者: Expertise 時間: 2025-3-22 21:02
Field Manual of Diseases on Trees and Shrubsops at an identity state. We show that, for this presentation of finite groups, the uniform word problem is .-complete. Here, the input consists of a finitary automaton together with a finite state sequence and the question is whether the sequence acts trivially on all input words. Additionally, we 作者: 伴隨而來 時間: 2025-3-23 00:10 作者: Inferior 時間: 2025-3-23 03:34
Field Manual of Diseases on Trees and Shrubsed if there is exactly one accepting path in its computation tree. If there are none or more than one accepting paths, the input is rejected. It turns out that, from a descriptional complexity point of view, .s differ significantly from the known types of finite automata. In particular the state cos作者: 驚惶 時間: 2025-3-23 07:03 作者: nocturnal 時間: 2025-3-23 13:06
https://doi.org/10.1007/978-94-007-5980-0more, when the counter is bounded by a constant, its value cannot be limited by any recursive function in the size of the machine. We consider three measures: the costs of all computations (. measure), all accepting computations (. measure), and the least expensive accepting computation (. measure).作者: 誘使 時間: 2025-3-23 14:53 作者: 哄騙 時間: 2025-3-23 19:55
Field Manual of Diseases on Trees and Shrubsength of a bordered box repetition-free word is at most ., with ., where . denotes the size of the alphabet. An alternative approach is given to prove that .(.) is an upper bound, which enables a proof that this upper bound is tight.作者: 冷淡一切 時間: 2025-3-23 23:35
,A Tight Upper Bound on?the?Length of?Maximal Bordered Box Repetition-Free Words,ength of a bordered box repetition-free word is at most ., with ., where . denotes the size of the alphabet. An alternative approach is given to prove that .(.) is an upper bound, which enables a proof that this upper bound is tight.作者: 音樂學(xué)者 時間: 2025-3-24 03:10
Descriptional Complexity of Formal Systems978-3-031-34326-1Series ISSN 0302-9743 Series E-ISSN 1611-3349 作者: 易于 時間: 2025-3-24 08:44
Field Manual of Diseases on Trees and Shrubsength of a bordered box repetition-free word is at most ., with ., where . denotes the size of the alphabet. An alternative approach is given to prove that .(.) is an upper bound, which enables a proof that this upper bound is tight.作者: Musculoskeletal 時間: 2025-3-24 14:31 作者: 束以馬具 時間: 2025-3-24 14:54 作者: 美食家 時間: 2025-3-24 19:29 作者: 抱狗不敢前 時間: 2025-3-24 23:22 作者: Gerontology 時間: 2025-3-25 07:12 作者: 熱情的我 時間: 2025-3-25 09:40
,Operational State Complexity Revisited: The Contribution of?Monsters and?Modifiers,imal state complexity of the languages . where . are languages with given state complexities. We highlight two tools that have been developed in recent years and which theorise and summarise a large number of methods used since the 1970?s. A monster is an automaton where any function from states to 作者: 我要沮喪 時間: 2025-3-25 14:30
,Hypercubes and?Isometric Words Based on?Swap and?Mismatch Distance,ming distance 1. We consider an edit distance based on swaps and mismatches, to which we refer as ., and define the . with edges linking words at tilde-distance 1. Then, we introduce and study some isometric subgraphs of the tilde-hypercube obtained by using special words called .. The subgraphs kee作者: 龍蝦 時間: 2025-3-25 17:57
,Defying Gravity and?Gadget Numerosity: The Complexity of?the?Hanano Puzzle,em (a .-complete problem that is very convenient to prove the .-hardness of reversible games with pushing blocks). Direct use of this property introduces an explosion in the number of gadgets needed to show .-hardness, but we show how to bring that number from 32 down to only three in general, and d作者: 能夠支付 時間: 2025-3-25 22:45 作者: Flu表流動 時間: 2025-3-26 02:21
,On Jaffe’s Pumping Lemma, Revisited, perspective. Jaffe’s pumping lemma is a necessary and sufficient condition for a language for being regular. In this way we improve a result of [.. A note on the pumping lemma for regular languages. ., 9(3):135–136, 1979] by showing that there is a regular language over the alphabet?. of size at le作者: 摻和 時間: 2025-3-26 05:29 作者: Heterodoxy 時間: 2025-3-26 11:15
,The Word Problem for?Finitary Automaton Groups,ops at an identity state. We show that, for this presentation of finite groups, the uniform word problem is .-complete. Here, the input consists of a finitary automaton together with a finite state sequence and the question is whether the sequence acts trivially on all input words. Additionally, we 作者: 庇護 時間: 2025-3-26 14:06 作者: dominant 時間: 2025-3-26 19:08
,Complexity of?Exclusive Nondeterministic Finite Automata,ed if there is exactly one accepting path in its computation tree. If there are none or more than one accepting paths, the input is rejected. It turns out that, from a descriptional complexity point of view, .s differ significantly from the known types of finite automata. In particular the state cos作者: FOR 時間: 2025-3-26 22:50
,Shortest Accepted Strings for?Two-Way Finite Automata: Approaching the?, Lower Bound,s paper, a family of .-state automata with shortest accepted strings of length . is constructed, thus improving the lower bound. For the special case of direction-determinate automata (those that always remember in the current state whether the last move was to the left or to the right), the maximum作者: annexation 時間: 2025-3-27 04:54 作者: conservative 時間: 2025-3-27 06:52
,Merging Two Hierarchies of?External Contextual Grammars with?Subregular Selection,es. In the past, two independent hierarchies have been obtained for external and internal contextual grammars, one based on selection languages defined by structural properties (finite, monoidal, nilpotent, combinational, definite, ordered, non-counting, power-separating, suffix-closed, commutative,作者: 消息靈通 時間: 2025-3-27 12:27
,A Tight Upper Bound on?the?Length of?Maximal Bordered Box Repetition-Free Words,ength of a bordered box repetition-free word is at most ., with ., where . denotes the size of the alphabet. An alternative approach is given to prove that .(.) is an upper bound, which enables a proof that this upper bound is tight.作者: 常到 時間: 2025-3-27 14:23
,Pushdown and?One-Counter Automata: Constant and Non-constant Memory Usage, counter grows at least as a logarithmic function. This bound can be reached. This is in contrast with the case of pushdown automata in which the optimal bound is double logarithmic. For the . and . measures these bounds are shown to be linear, for both pushdown and one-counter automata.作者: 后來 時間: 2025-3-27 18:48 作者: 財產(chǎn) 時間: 2025-3-27 23:57 作者: 來自于 時間: 2025-3-28 02:39
,Shortest Accepted Strings for?Two-Way Finite Automata: Approaching the?, Lower Bound,of direction-determinate automata (those that always remember in the current state whether the last move was to the left or to the right), the maximum length of the shortest accepted string is determined precisely as ..作者: TERRA 時間: 2025-3-28 08:53
Conference proceedings 2023iewed and selected from 16 submissions. The conference focus on all aspects of descriptional complexity, including automata, grammars, languages, and other formal systems; various modes of operations and complexity measures..作者: MURKY 時間: 2025-3-28 10:47 作者: Gene408 時間: 2025-3-28 14:47 作者: mastopexy 時間: 2025-3-28 22:40
https://doi.org/10.1007/978-94-007-6076-9at finiteness of existential and universal width of an AFA is decidable. Also we give hardness results and give an algorithm to decide whether the existential or universal width of an AFA is bounded by a given integer.作者: sundowning 時間: 2025-3-28 23:30
Field Manual of Diseases on Trees and Shrubswitnesses are described over a four-letter alphabet for cut, and a ten-letter alphabet for square. We also show that the tight upper bound on the syntactic complexity of a language given by an?.-state NFA is .. For the square root operation, we provide a lower bound?. and an upper bound?..作者: 平淡而無味 時間: 2025-3-29 05:39
Field Manual of Diseases on Trees and Shrubsalso show that the respective compressed word problem, where the state sequence is given as a straight-line program, is .-complete. In both cases, we give a direct reduction from the satisfiablity problem for (quantified) boolean formulae.作者: ROOF 時間: 2025-3-29 10:29 作者: correspondent 時間: 2025-3-29 12:51 作者: GEST 時間: 2025-3-29 18:16 作者: 集合 時間: 2025-3-29 19:45 作者: 修正案 時間: 2025-3-30 02:46 作者: Mortal 時間: 2025-3-30 08:02 作者: 遷移 時間: 2025-3-30 08:46 作者: ACRID 時間: 2025-3-30 13:51
Field Manual of Diseases on Trees and Shrubsn the other hand, .s may have advantages in comparison to .s. A tight bound is given by . states for the simulation by .s. Finally, we investigate the computational complexity of different decision problems for .s and it turns out that emptiness, universality, inclusion, and equivalence are .-complete.作者: 性上癮 時間: 2025-3-30 20:25
,On Jaffe’s Pumping Lemma, Revisited,arch on minimal pumping constants for various pumping lemma conducted in [. and .. Operational complexity and pumping lemmas. ., 59:337–355, 2022]. Moreover, we also compare the minimal pumping constant of Jaffe’s pumping lemma with those of other well-known pumping lemmata from the literature.作者: ECG769 時間: 2025-3-31 00:17
,Complexity of?Exclusive Nondeterministic Finite Automata,n the other hand, .s may have advantages in comparison to .s. A tight bound is given by . states for the simulation by .s. Finally, we investigate the computational complexity of different decision problems for .s and it turns out that emptiness, universality, inclusion, and equivalence are .-complete.
