The search functionality is under construction.
The search functionality is under construction.

Keyword Search Result

[Keyword] languagetheory(1hit)

1-1hit
  • A Fast Algorithm for Checking the Inclusion for Very Simple Deterministic Pushdown Automata

    Mitsuo WAKATSUKI  Etsuji TOMITA  

     
    PAPER-Automaton, Language and Theory of Computing

      Vol:
    E76-D No:10
      Page(s):
    1224-1233

    We are concerned with a subclass of deterministic pushdown automata (dpda) called very simple dpda's, and present a new direct branching algorithm for checking the inclusion for a pair of languages accepted by these dpda's. As usual, we take the maximal thickness (i.e., the length of the shortest input strings that make each stack symbol go to empry) of all stack symbols into account as one parameter of the given dpda's. Then the worst-case time complexity of our algorithm is polynomial with respect to these parameters. Without considering the thickness, the complexity is single exponential in the description length of the given dpda's. As far as we are concerned with very simple dpda's, our algorithm is very simple and direct, and is faster and much better than the previously given algorithms for the inclusion problem of dpda's.