518 citations
- Australian National UniversityAU8 papers
- California Institute of TechnologyUS8 papers
- Durham UniversityGB8 papers
- University of EdinburghGB8 papers
- Herzberg Institute of AstrophysicsCA7 papers
- McMaster UniversityCA7 papers
- Royal Military College of CanadaCA7 papers
- University of CambridgeGB7 papers
- Massachusetts Institute of TechnologyUS6 papers
- Max Planck Institute for AstronomyDE6 papers
- Swinburne University of TechnologyAU6 papers
- Western UniversityCA6 papers
5 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…
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…