14 citations · 19 across the 4 of their papers we have counts for
4 papers · 1 filter
Finite-State Complexity and the Size of Transducers
Cristian Calude, Kai Salomaa, Tania Roblot
Finite-state complexity is a variant of algorithmic information theory obtained by replacing Turing machines with finite transducers. We consider the state-size of transducers need…
Nondeterministic State Complexity for Suffix-Free Regular Languages
Yo-Sub Han, Kai Salomaa
We investigate the nondeterministic state complexity of basic operations for suffix-free regular languages. The nondeterministic state complexity of an operation is the number of s…
Transformations Between Different Types of Unranked Bottom-Up Tree Automata
Xiaoxue Piao, Kai Salomaa
We consider the representational state complexity of unranked tree automata. The bottom-up computation of an unranked tree automaton may be either deterministic or nondeterministic…
Transition Complexity of Incomplete DFAs
Yuan Gao, Kai Salomaa, Sheng Yu
In this paper, we consider the transition complexity of regular languages based on the incomplete deterministic finite automata. A number of results on Boolean operations have been…