Skip to content
Publications

Article · May 1, 2000

A redefinition of Embedded Push-Down Automata ∗

Miguel Á. Alonso, Éric Villemonte de la Clergerie, Jesús Vilares

Abstract

A new definition of Embedded Push-Down Automata is provided. We prove this new definition preserves the equivalence with tree adjoining languages and we provide a tabulation framework to execute any automaton in polynomial time with respect to the length of the input string. 1.

semigroups and automata theorySyntax, Semantics, Linguistic VariationAlgorithms and Data Compressionautomaton equivalencetabulationformal language theory

More by Miguel Alonso