Titlebook: Descriptional Complexity of Formal Systems; 24th IFIP WG 1.02 In Yo-Sub Han,György Vaszil Conference proceedings 2022 IFIP International Fe

魔鬼在游行

,On the Power of Recursive Word-Functions Without Concatenation,ds allows to address words directly and not through some integer encoding (of exponential size). Considering alphabets with at least two symbols allows to relate simply and naturally to complexity theory. Indeed, the polynomial-time complexity class (as well as . and exponential time) corresponds to

投射

口诀法

,Nearly ,-Universal Words - Investigating a Part of Simon’s Congruence, of scattered factors (also known as subwords or subsequences), which are parts of the word in the correct order but not necessarily consecutive, e.g., . is a scattered factor of . but . is not. Following the idea of scattered factor .-universality (also known as .-richness), we investigate nearly .

熔岩

State Complexity of Binary Coded Regular Languages,ton (DFA) . with . states recognizing a language . over ., we consider the problem of how many states we need for an automaton . that decides membership in ., the binary coded version of .. Namely, . accepts binary inputs belonging to . and rejects binary inputs belonging to ., where . is the comple

allude

威胁你

存在主义

,Operations on Subregular Languages and Nondeterministic State Complexity,combinational, finitely generated left ideal, group, star, comet, two-sided comet, ordered, and power-separating languages, and consider the operations of intersection, union, concatenation, power, Kleene star, reversal, and complementation. We get the exact complexity in all cases, except for compl

BLINK

听写

urethritis

Lazy Regular Sensing,uitively, the sensing cost quantifies the detail in which a random input word has to be read in order to decide its membership in the language, when the input letters composing the word are truth assignments to a finite set of .. We introduce the notion of ., where the signals are not sensed simulta