14 citations · 33 across the 10 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…
Operational State Complexity of Deterministic Unranked Tree Automata
Xiaoxue Piao, Kai Salomaa
We consider the state complexity of basic operations on tree languages recognized by deterministic unranked tree automata. For the operations of union and intersection the upper an…
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…