Computing and Informatics / Computers and Artificial Intelligence · 2012 · 10 citations · 3 references
ComputingComputer ScienceAlgorithmsComputer ArchitectureFormal MethodsAlgorithm AnalysisAutomata TheoryFinite AutomataSimulation MethodsSimulation OptimizationSystem SimulationAsymptotic AnalysisAutomata SimulationKripke StructuresSimulation Optimization AlgorithmsSimulation PreorderTransition SystemsTree Automata
When comparing the fastest algorithm for computing the largest simulation preorder over Kripke structures with the one for labeled transition systems (LTS), there is a noticeable time and space complexity blow-up proportional to the size of the alphabet of an LTS. In this paper, we present optimizations that suppress this increase of complexity and may turn a large alphabet of an LTS to an advantage. Our experimental results show significant speed-ups and memory savings. Moreover, the optimized algorithm allows one to improve asymptotic complexity of procedures for computing simulations over tree automata using recently proposed algorithms based on computing simulation over certain special LTS derived from a tree automaton.
3
Tree automata techniques and applications
Hubert Comon, Max Dauchet, Florent Jacquemard et al. · 1997 · 1.2K citations · Full text
Computing simulations on finite and infinite graphs
Monika Henzinger, Thomas A. Henzinger, Peter W. Kopke · 2002 · 479 citations
A New Efficient Simulation Equivalence Algorithm
Francesco Ranzato, Francesco Tapparo · 2007 · 45 citations · Full text