標(biāo)題: Titlebook: Descriptional Complexity of Formal Systems; 20th IFIP WG 1.02 In Stavros Konstantinidis,Giovanni Pighizzini Conference proceedings 2018 IFI [打印本頁] 作者: 熱情美女 時(shí)間: 2025-3-21 17:41
書目名稱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é)科排名
作者: Gastric 時(shí)間: 2025-3-21 21:12 作者: 為現(xiàn)場 時(shí)間: 2025-3-22 02:53
Most Complex Deterministic Union-Free Regular Languages,ar and boolean operations. We also show that the tight upper bounds on the state complexity of binary operations that take arguments over different alphabets are the same as those for arbitrary regular languages. Furthermore, we prove that the maximal syntactic semigroup of a union-free language has作者: Eeg332 時(shí)間: 2025-3-22 05:59
State Grammars with Stores,ith a pushdown and reversal-bounded counters, and these are surprisingly shown to be strictly weaker than state grammars with the standard derivation relation (and no counters). Complexity results of some decision problems involving state grammars with counters are also studied.作者: animated 時(shí)間: 2025-3-22 11:40 作者: 是限制 時(shí)間: 2025-3-22 15:06 作者: 是限制 時(shí)間: 2025-3-22 20:35
Word Problem Languages for Free Inverse Monoids,oid has context-free word problem; that the word problem of the free inverse monoid of rank 1 is both 2-context-free (an intersection of two context-free languages) and ET0L; that the co-word problem of the free inverse monoid of rank 1 is context-free; and that the word problem of a free inverse mo作者: jungle 時(shí)間: 2025-3-22 22:48
Most Complex Deterministic Union-Free Regular Languages,ed by a deterministic . finite automaton; this is an automaton which has one final state and exactly one cycle-free path from any state to the final state. Jirásková and Masopust proved that the state complexities of the basic operations reversal, star, product, and boolean operations in determinist作者: concise 時(shí)間: 2025-3-23 03:32
Site-Directed Insertion: Decision Problems, Maximality and Minimality,ate strings by overlapping a suffix and a prefix of the argument strings. We consider decision problems and language equations involving site-directed insertion. By relying on the tools provided by . we show that one variable equations involving site-directed insertion and regular constants can be s作者: 門閂 時(shí)間: 2025-3-23 09:04 作者: 太空 時(shí)間: 2025-3-23 13:24 作者: 天真 時(shí)間: 2025-3-23 15:35
Forward Injective Finite Automata: Exact and Random Generation of Nonisomorphic NFAs,?to isomorphism. Using this representation an enumeration is given and an efficient uniform random generator is presented. We provide a conversion algorithm from a nondeterministic finite automaton or regular expression into an equivalent FIFA. Finally, we present some experimental results comparing作者: 無法解釋 時(shí)間: 2025-3-23 18:19
A Local Limit Property for Pattern Statistics in Bicomponent Stochastic Models,c model for the random generation is defined by a rational formal series with non-negative real coefficients. The result yields a local limit towards a uniform density function and holds under the assumption that the formal series defining the model is recognized by a weighted finite state automaton作者: 英寸 時(shí)間: 2025-3-24 01:44 作者: Mawkish 時(shí)間: 2025-3-24 05:21
Cover Complexity of Finite Languages,ive a characterisation of the situations in which they collapse to a bounded complexity measure. Moreover, we show for a restricted class of context-free grammars that its grammatical cover complexity measure w.r.t. a finite language . is unbounded and that the cover complexity of . can be computed 作者: 好忠告人 時(shí)間: 2025-3-24 09:01 作者: 輕率的你 時(shí)間: 2025-3-24 12:04 作者: TOM 時(shí)間: 2025-3-24 15:46 作者: 低能兒 時(shí)間: 2025-3-24 19:05
State Complexity of Unambiguous Operations on Deterministic Finite Automata,enation, and Kleene star operations on formal languages. For the disjoint union of languages represented by an .-state and an .-state DFA, the state complexity is .; for the unambiguous concatenation, it is known to be . (Daley et al. “Orthogonal concatenation: Language equations and state complexit作者: Priapism 時(shí)間: 2025-3-24 23:46
Cycle Height of Finite Automata, has cycle height . for some .. We give a polynomial time algorithm to decide whether an NFA has finite cycle height and, in the positive case, to compute its optimal cycle height. Nondeterministic finite automata of finite cycle height recognize the polynomial density regular languages.作者: 暗指 時(shí)間: 2025-3-25 04:41 作者: Immunoglobulin 時(shí)間: 2025-3-25 08:11 作者: ostrish 時(shí)間: 2025-3-25 14:09 作者: Priapism 時(shí)間: 2025-3-25 16:04
Electroweak Interactions of Quarksity function is determined to be .. In the case of a unary alphabet, disjoint union requires up?to . states, unambiguous concatenation has state complexity ., and unambiguous star requires . states in the worst case.作者: entreat 時(shí)間: 2025-3-25 21:49
Spontaneous Global Symmetry Breakingstate complexity of the Boolean operations as well as the operations concatenation and iteration is investigated, where tight upper and lower bounds are derived for unary as well as arbitrary alphabets under the condition that the corresponding language classes are closed under the operation considered.作者: Morsel 時(shí)間: 2025-3-26 01:28 作者: antidepressant 時(shí)間: 2025-3-26 05:02
State Complexity of Unambiguous Operations on Deterministic Finite Automata,ity function is determined to be .. In the case of a unary alphabet, disjoint union requires up?to . states, unambiguous concatenation has state complexity ., and unambiguous star requires . states in the worst case.作者: remission 時(shí)間: 2025-3-26 11:58 作者: Pageant 時(shí)間: 2025-3-26 16:11
A New Technique for Reachability of States in Concatenation Automata,tion automata. We prove some results that seem to capture the essence of many of these induction arguments. Using these results, reachability proofs in concatenation automata can often be done more simply and without using induction directly.作者: 令人悲傷 時(shí)間: 2025-3-26 17:19 作者: MARS 時(shí)間: 2025-3-26 22:03 作者: 有組織 時(shí)間: 2025-3-27 05:11
On the Grammatical Complexity of Finite Languages,y measure and varying the grammar type. In both of these cases, we develop an almost complete picture, which gives new and interesting insights into the old topic of grammatical production complexity.作者: Glossy 時(shí)間: 2025-3-27 05:45 作者: 磨坊 時(shí)間: 2025-3-27 10:31 作者: nutrition 時(shí)間: 2025-3-27 15:46 作者: echnic 時(shí)間: 2025-3-27 19:48
Nikita V. Kitov,Mikhail V. Volkova uniform density function and holds under the assumption that the formal series defining the model is recognized by a weighted finite state automaton with two primitive components having equal dominant eigenvalue.作者: ALLAY 時(shí)間: 2025-3-28 01:50
G. Manara,S. Mugnaini,P. Nepa,A. A. Serraon can be transformed into an halting linear-time equivalent one. We also obtain polynomial transformations into related models, including weight-reducing Hennie machines, and we show exponential gaps for converse transformations in the deterministic case.作者: Gratulate 時(shí)間: 2025-3-28 05:29 作者: 泛濫 時(shí)間: 2025-3-28 08:25
Word Problem Languages for Free Inverse Monoids,ree languages) and ET0L; that the co-word problem of the free inverse monoid of rank 1 is context-free; and that the word problem of a free inverse monoid of rank greater than 1 is not poly-context-free.作者: engrossed 時(shí)間: 2025-3-28 11:49 作者: 非秘密 時(shí)間: 2025-3-28 16:51
A Local Limit Property for Pattern Statistics in Bicomponent Stochastic Models,a uniform density function and holds under the assumption that the formal series defining the model is recognized by a weighted finite state automaton with two primitive components having equal dominant eigenvalue.作者: 薄荷醇 時(shí)間: 2025-3-28 20:20 作者: 冷漠 時(shí)間: 2025-3-29 01:33
Further Closure Properties of Input-Driven Pushdown Automata,n requires . states, as long as . is well-nested; deletion is representable with 2. states, for well-nested .; square root requires . states, for well-nested .; the well-nested subset of the first half is representable with . states. Without the well-nestedness constraints, non-closure is established in each case.作者: A精確的 時(shí)間: 2025-3-29 04:07
0302-9743 l working conference concerning the descriptional complexity of formal systems and structures and its applications. Topics of interest are related to all aspects of descriptional complexity and much more.?.978-3-319-94630-6978-3-319-94631-3Series ISSN 0302-9743 Series E-ISSN 1611-3349 作者: Endemic 時(shí)間: 2025-3-29 09:29
P-NET-Management über das Internettion automata. We prove some results that seem to capture the essence of many of these induction arguments. Using these results, reachability proofs in concatenation automata can often be done more simply and without using induction directly.作者: integral 時(shí)間: 2025-3-29 14:03 作者: 羊齒 時(shí)間: 2025-3-29 17:57 作者: FUSC 時(shí)間: 2025-3-29 20:00
Modular Dissipation Analysis for QCAata-theoretic randomness of infinite sequences in connection with automata-independent notions like disjunctivity and Borel normality..On the other hand it considers the scale of relaxations of randomness (Borel normality and disjunctivity), that is, finite-state dimension and subword complexity and作者: MONY 時(shí)間: 2025-3-30 02:01
Craig S. Lent,Gregory L. Sniderg automata that process the input in a discontinuous way with the restriction that the input head reads deterministically from left-to-right starting from the leftmost letter in the input and when it reaches the end of the input word, it returns to the beginning and continues the computation. We sol作者: 敵意 時(shí)間: 2025-3-30 05:30 作者: 建筑師 時(shí)間: 2025-3-30 12:13
Field-Scale Water and Solute Flux in Soilsed by a deterministic . finite automaton; this is an automaton which has one final state and exactly one cycle-free path from any state to the final state. Jirásková and Masopust proved that the state complexities of the basic operations reversal, star, product, and boolean operations in determinist作者: 拔出 時(shí)間: 2025-3-30 15:45 作者: 制定 時(shí)間: 2025-3-30 16:43
Martin Wollschlaeger,Erik Unger,Heiko Witteay have undefined behaviour. We prove that it is decidable whether this behaviour is defined, and, if it is, we show that two-way automata over locally finite semirings are equivalent to one-way automata.作者: brassy 時(shí)間: 2025-3-31 00:42
P-NET-Management über das Internetes. Such demonstrations are a necessary step in establishing the state complexity of the concatenation of two languages, and thus in establishing the state complexity of concatenation as an operation. Typically, ad-hoc induction arguments are used to show particular states are reachable in concatena作者: 傳染 時(shí)間: 2025-3-31 01:04 作者: grieve 時(shí)間: 2025-3-31 05:55 作者: Jubilation 時(shí)間: 2025-3-31 10:34
G. Manara,S. Mugnaini,P. Nepa,A. A. Serraly, it may use quadratic time in the input length. We show that, with a polynomial increase in size and preserving determinism, each 1-limited automaton can be transformed into an halting linear-time equivalent one. We also obtain polynomial transformations into related models, including weight-redu作者: 變化 時(shí)間: 2025-3-31 15:59
Conference proceedings 20041st editionive a characterisation of the situations in which they collapse to a bounded complexity measure. Moreover, we show for a restricted class of context-free grammars that its grammatical cover complexity measure w.r.t. a finite language . is unbounded and that the cover complexity of . can be computed 作者: dissolution 時(shí)間: 2025-3-31 20:50
Conference proceedings 20041st editionttered cover, and (ii) whether the underlying grammar generates a finite or infinite language. In case the generated language is infinite, the intersection with all words up?to a certain length has to be considered in order to obtain the finite language under consideration. In this way, we obtain si作者: Expand 時(shí)間: 2025-3-31 22:57
https://doi.org/10.1007/3-540-08347-2nt state matches the state in the production. Once states are added to grammars, it is natural to add various stores, similar to machine models. With such extensions, productions can only be applied if both the state and the value read from each store matches between the current sentential form and
