標(biāo)題: Titlebook: Descriptional Complexity of Formal Systems; 18th IFIP WG 1.2 Int Cezar Campeanu,Florin Manea,Jeffrey Shallit Conference proceedings 2016 IF [打印本頁(yè)] 作者: 惡夢(mèng) 時(shí)間: 2025-3-21 17:56
書(shū)目名稱Descriptional Complexity of Formal Systems影響因子(影響力)
書(shū)目名稱Descriptional Complexity of Formal Systems影響因子(影響力)學(xué)科排名
書(shū)目名稱Descriptional Complexity of Formal Systems網(wǎng)絡(luò)公開(kāi)度
書(shū)目名稱Descriptional Complexity of Formal Systems網(wǎng)絡(luò)公開(kāi)度學(xué)科排名
書(shū)目名稱Descriptional Complexity of Formal Systems被引頻次
書(shū)目名稱Descriptional Complexity of Formal Systems被引頻次學(xué)科排名
書(shū)目名稱Descriptional Complexity of Formal Systems年度引用
書(shū)目名稱Descriptional Complexity of Formal Systems年度引用學(xué)科排名
書(shū)目名稱Descriptional Complexity of Formal Systems讀者反饋
書(shū)目名稱Descriptional Complexity of Formal Systems讀者反饋學(xué)科排名
作者: 打折 時(shí)間: 2025-3-21 22:53 作者: 沒(méi)有希望 時(shí)間: 2025-3-22 03:27
https://doi.org/10.1007/978-3-031-41574-6We survey recent results on the descriptional complexity of self-verifying finite automata. In particular, we discuss the cost of simulation of self-verifying finite automata by deterministic finite automata, and the complexity of basic regular operations on languages represented by self-verifying finite automata.作者: 無(wú)能力之人 時(shí)間: 2025-3-22 07:42
Computer Supported Cooperative WorkWe show that it is decidable given an MSO-definable property . of countable words and a Muller context-free grammar ., whether every word in the language generated by . satisfies ..作者: 起草 時(shí)間: 2025-3-22 09:52
Completely Reachable Automata,We present a few results and several open problems concerning complete deterministic finite automata in which every non-empty subset of the state set occurs as the image of the whole state set under the action of a suitable input word.作者: Malcontent 時(shí)間: 2025-3-22 12:55 作者: Malcontent 時(shí)間: 2025-3-22 20:59
Self-Verifying Finite Automata and Descriptional Complexity,We survey recent results on the descriptional complexity of self-verifying finite automata. In particular, we discuss the cost of simulation of self-verifying finite automata by deterministic finite automata, and the complexity of basic regular operations on languages represented by self-verifying finite automata.作者: apropos 時(shí)間: 2025-3-23 00:24 作者: penance 時(shí)間: 2025-3-23 02:56 作者: 特別容易碎 時(shí)間: 2025-3-23 09:29
The Irreplaceable Experience of Fieldworkd a minimal .-state DFA ., both?defined over an alphabet . with ., such that the minimal DFA for the language .(.).(.) has exactly . states. This improves a?similar result in the literature that uses an exponential alphabet.作者: Multiple 時(shí)間: 2025-3-23 12:36 作者: 突襲 時(shí)間: 2025-3-23 17:25
Ma?gorzata Oleszkiewicz-PeralbaZemek in 2012 [.]. Second, we close a study started by ?erno and Mráz in 2010 [.] by proving that a clearing restarting automaton using contexts of length two can accept a binary non-context-free language.作者: narcissism 時(shí)間: 2025-3-23 19:54 作者: Contend 時(shí)間: 2025-3-23 22:40 作者: BARGE 時(shí)間: 2025-3-24 04:06 作者: 相同 時(shí)間: 2025-3-24 07:51 作者: MODE 時(shí)間: 2025-3-24 11:21 作者: 晚來(lái)的提名 時(shí)間: 2025-3-24 16:57
Affective-Focused Geographical Fieldworkt of infinite words is weakly recognizable by such a morphism if and only if it is accepted by some Büchi automaton. We consider the descriptional complexity of various constructions for weakly recognizing morphisms. This includes the conversion from and to Büchi automata, the conversion into strong作者: 注入 時(shí)間: 2025-3-24 19:43 作者: IST 時(shí)間: 2025-3-25 00:52 作者: 五行打油詩(shī) 時(shí)間: 2025-3-25 05:30
Michael Flecker,Teddy Y. H. Simcerns the structure of the minimum automaton accepting the language under consideration. It is also observed that there exist reduced reversible automata which are not minimal, in the sense that all the automata obtained by merging some of their equivalent states are irreversible. Furthermore, it is作者: Induction 時(shí)間: 2025-3-25 08:24 作者: neuron 時(shí)間: 2025-3-25 12:45
Hwee Hwang Sim,Shiang Swee Grace Liowwer bounds for the size of the minimal deterministic finite automaton (DFA) needed for the radius . prefix distance neighbourhood of an . state DFA that recognizes, respectively, a finite, a prefix-closed and a prefix-free language. For prefix-closed languages the lower bound automata are defined ov作者: Inexorable 時(shí)間: 2025-3-25 18:16
Ma?gorzata Oleszkiewicz-PeralbaZemek in 2012 [.]. Second, we close a study started by ?erno and Mráz in 2010 [.] by proving that a clearing restarting automaton using contexts of length two can accept a binary non-context-free language.作者: endoscopy 時(shí)間: 2025-3-25 22:28 作者: miracle 時(shí)間: 2025-3-26 01:45
Unary Self-verifying Symmetric Difference Automata,We show that there is a family of languages . which can always be represented non-trivially by unary SV-XNFA. We also consider the descriptional complexity of unary SV-XNFA, giving an upper and lower bound for state complexity.作者: Immobilize 時(shí)間: 2025-3-26 07:40 作者: EXALT 時(shí)間: 2025-3-26 10:32
Cezar Campeanu,Florin Manea,Jeffrey ShallitIncludes supplementary material: 作者: 因無(wú)茶而冷淡 時(shí)間: 2025-3-26 16:14 作者: 平 時(shí)間: 2025-3-26 20:24
https://doi.org/10.1007/978-3-319-41114-9automata theory; context free languages; formal languages; regular languages; turing machines; automata e作者: 卡死偷電 時(shí)間: 2025-3-26 23:24 作者: 鈍劍 時(shí)間: 2025-3-27 02:00
On the State Complexity of Partial Derivative Automata For Regular Expressions with Intersection,sions extended with intersection only (also called semi-extended) can already be exponentially smaller than standard regular expressions or equivalent nondeterministic finite automata (.). For practical purposes it is important to study the average behaviour of conversions between these models. In t作者: 特別容易碎 時(shí)間: 2025-3-27 05:49
Unrestricted State Complexity of Binary Operations on Regular Languages,cted to be over the same alphabet, with . and . quotients, respectively, the state complexity of any binary boolean operation on . and . is ., and that of the product (concatenation) is .. In contrast to this, I show that if . and . are over their own different alphabets, the state complexity of uni作者: Accessible 時(shí)間: 2025-3-27 10:30 作者: licence 時(shí)間: 2025-3-27 17:16
Contextual Array Grammars with Matrix and Regular Control,nal contextual array grammars are less powerful than matrix contextual array grammars, which themselves are less powerful than contextual array grammars with regular control languages. Yet in the 1-dimensional case, for a one-letter alphabet, the family of 1-dimensional array languages generated by 作者: DOSE 時(shí)間: 2025-3-27 19:56 作者: 有幫助 時(shí)間: 2025-3-28 00:27 作者: 柱廊 時(shí)間: 2025-3-28 05:39
Descriptional Complexity of Bounded Regular Languages,e costs for the determinization of nondeterministic finite automata accepting strongly bounded regular languages. The upper bound for the costs is larger than the costs for determinizing unary regular languages, but lower than the costs for determinizing arbitrary regular languages. In the second pa作者: Hyaluronic-Acid 時(shí)間: 2025-3-28 06:40
The Complexity of Languages Resulting from the Concatenation Operation,d a minimal .-state DFA ., both?defined over an alphabet . with ., such that the minimal DFA for the language .(.).(.) has exactly . states. This improves a?similar result in the literature that uses an exponential alphabet.作者: 偏離 時(shí)間: 2025-3-28 12:22
Minimal and Reduced Reversible Automata,cerns the structure of the minimum automaton accepting the language under consideration. It is also observed that there exist reduced reversible automata which are not minimal, in the sense that all the automata obtained by merging some of their equivalent states are irreversible. Furthermore, it is作者: 匍匐前進(jìn) 時(shí)間: 2025-3-28 16:02 作者: legacy 時(shí)間: 2025-3-28 19:43
State Complexity of Prefix Distance of Subregular Languages,wer bounds for the size of the minimal deterministic finite automaton (DFA) needed for the radius . prefix distance neighbourhood of an . state DFA that recognizes, respectively, a finite, a prefix-closed and a prefix-free language. For prefix-closed languages the lower bound automata are defined ov作者: brassy 時(shí)間: 2025-3-29 00:25 作者: MENT 時(shí)間: 2025-3-29 04:00
Conference proceedings 2016harest, Romania, in July 2016. The 13 full papers presentedtogether with 4 invited talks were carefully reviewed and selected from21 submissions.Descriptional Complexity is a ?eld in Computer Science that deals with the size of all kind of objects that occur in computational models, such as Turing M作者: 啪心兒跳動(dòng) 時(shí)間: 2025-3-29 10:36
Contextual Array Grammars with Matrix and Regular Control,contextual array grammars with regular control languages coincides with the family of regular 1-dimensional array languages, whereas for alphabets with more than one letter, we obtain the array images of the linear languages.作者: Missile 時(shí)間: 2025-3-29 13:14 作者: Harness 時(shí)間: 2025-3-29 18:05
Minimal and Reduced Reversible Automata, proved that if the minimum deterministic automaton accepting a reversible language contains a loop in the “irreversible part” then it is always possible to construct infinitely many reduced reversible automata accepting such a language.作者: 獨(dú)特性 時(shí)間: 2025-3-29 22:33
State Complexity of Prefix Distance of Subregular Languages,er a binary alphabet. For finite and prefix-free regular languages the lower bound constructions use an alphabet that depends on the size of the DFA and it is shown that the size of the alphabet is optimal.作者: 江湖郎中 時(shí)間: 2025-3-30 00:32
0302-9743 r in computational models, such as Turing Machines, ?nte automata, grammars, splicing systems and others. The topics of this conference are related to all aspects of descriptional complexity.?.978-3-319-41113-2978-3-319-41114-9Series ISSN 0302-9743 Series E-ISSN 1611-3349 作者: Inflammation 時(shí)間: 2025-3-30 06:55
https://doi.org/10.1007/978-1-84628-768-8 bound can be met if all .(.,?.) states are reachable. We know that an alphabet of size at least . is required provided that .. The question of reachability, and hence also of the tightness of the bound .(.,?.) in general, remains open.作者: machination 時(shí)間: 2025-3-30 10:02
Affective-Focused Geographical Fieldworksal, concatenation, and iteration. In detail, we present upper and lower bounds and we develop for the proof of the lower bounds a tool that exploits the number of different colorings of cycles occurring in deterministic finite automata accepting bounded languages.作者: FEAT 時(shí)間: 2025-3-30 16:17 作者: Phagocytes 時(shí)間: 2025-3-30 17:39 作者: Parallel 時(shí)間: 2025-3-30 21:59 作者: BLANC 時(shí)間: 2025-3-31 01:06
Operations on Weakly Recognizing Morphisms,plexity of various constructions for weakly recognizing morphisms. This includes the conversion from and to Büchi automata, the conversion into strongly recognizing morphisms, and complementation. For some problems, we are able to give more precise bounds in the case of binary alphabets or simple semigroups.作者: 幻想 時(shí)間: 2025-3-31 06:47 作者: Insufficient 時(shí)間: 2025-3-31 13:04 作者: 大猩猩 時(shí)間: 2025-3-31 14:45 作者: zonules 時(shí)間: 2025-3-31 20:44
