Paper Info
Title
A Fast Algorithm to Decide on the Equivalence of Stateless DPDA
Abstract
We give an algorithm to decide the equivalence of stateless dpda with acceptance on stack letters. This algorithm is polynomial in time and space in the valuation and the length of description of the compared automata, and exponential in the length of description, instead of the double exponential complexity of Oyamaguchi and Honda's algorithm.
Year
DOI
Venue
1993
10.1051/ita/1993270100231
RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS
Field
DocType
Volume
Automata theory,Combinatorics,Deterministic automaton,Algorithm complexity,Deterministic pushdown automaton,Algorithm,Equivalence (measure theory),ESPACE,Stateless protocol,Mathematics
Journal
27
Issue
Citations 
PageRank 
1
7
1.21
References 
Authors
6
1
Name
Order
Citations
PageRank
Didier Caucal147039.15