Titlebook: Descriptional Complexity of Formal Systems; 25th IFIP WG 1.02 In Henning Bordihn,Nicholas Tran,György Vaszil Conference proceedings 2023 IF

Gerontology

热情的我

,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

我要沮丧

,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

龙虾

,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

能够支付

Flu表流动

,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

掺和

Heterodoxy

,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

庇护

dominant

,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