Titlebook: Descriptional Complexity of Formal Systems; 22nd International C Galina Jirásková,Giovanni Pighizzini Conference proceedings 2020 Springer

松紧带

Mutually Accepting Capacitated Automata,. of CAs and view them as recognizers of . – sets of multisets of words, where a multiset . of words is in the multi-language of a CA . if all the words in . can be mutually accepted by .: the multiset of runs on all the words in . together respects the bounds induced by the capacities. Thus, capaci

GUEER

Bad Pictures: Some Structural Properties Related to Overlaps,s a bit-to-bit transformation from . to . such that any picture in the intermediate steps is .-free. Such transformation is called .-.. A binary picture is . if it is not good. These notions generalize to pictures the corresponding ones for strings. We study some properties of bad binary pictures in

fatuity

essential-fats

Crisp-Determinization of Weighted Tree Automata over Additively Locally Finite and Past-Finite Mono of the underlying weight algebra; weights different from these units may only appear at the root of the given input tree. A weighted tree automaton is crisp-determinizable if there exists an equivalent crisp-deterministic one. We prove that it is decidable whether weighted tree automata over additi

lattice

Acetaminophen

State Complexity Bounds for the Commutative Closure of Group Languages,is bounded by the number of states of the original automaton, raised to the power of the alphabet size, times the product of the order of the letters, viewed as permutations of the state set. This gives the asymptotic state bound ., if the original regular language is accepted by an automaton with .

Filibuster

Multiple Concatenation and State Complexity (Extended Abstract),ure. Then we use slightly modified Maslov’s automata to get witnesses over a .-letter alphabet which solves an open problem stated by Caron et al. [2018, Fund. Inform. 160, 255–279]. We prove that for ., the ternary alphabet is optimal. We also obtain lower bounds . and . in the binary and ternary c

Acetaldehyde

Combining Limited Parallelism and Nondeterminism in Alternating Finite Automata, (AFA), counts the number of branches which do not need to be traversed in an accepting computation (respectively, the maximum number of branches which can be ignored in any computation tree of the AFA). We also define the combined width (respectively, the maximal combined width), by combining this

条街道往前推

Longer Shortest Strings in Two-Way Finite Automata,FA) can be at least . symbols long, improved to . in their latest contribution. The lower bound was obtained using “direction-determinate” 2DFA, which always remember their direction of motion at the last step, and used an alphabet of size .. In this paper, the method of Dobronravov et al. is extend

十字架

Iterated Uniform Finite-State Transducers: Descriptional Complexity of Nondeterminism and Two-Way Ms on the output of the previous one. We consider devices with one-way motion and two-way motion, i.e., sweeps are either from left to right only, or alternate from left to right and from right to left. In addition, devices may work deterministically or nondeterministically. Here, we restrict to stud