✦ LIBER ✦

On the power of tree-walking automata

✍ Scribed by Frank Neven; Thomas Schwentick

Book ID: 114273338
Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 206 KB
Volume: 183
Category: Article
ISSN: 0890-5401
DOI: 10.1016/s0890-5401(03)00013-0

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

The minimalization of tree automata

✍ Walter S. Brainerd 📂 Article 📅 1968 🏛 Elsevier Science ⚖ 340 KB

The complexity of tree automata and XPat

The complexity of tree automata and XPath on grammar-compressed trees

✍ Markus Lohrey; Sebastian Maneth 📂 Article 📅 2006 🏛 Elsevier Science 🌐 English ⚖ 292 KB

On the computational power of pushdown a

On the computational power of pushdown automata

✍ A.V. Aho; J.D. Ullman; J.E. Hopcroft 📂 Article 📅 1970 🏛 Elsevier Science 🌐 English ⚖ 361 KB

We present a relation between the sets accepted by two-way pushdown automata and certain tape complexity classes of off-line Turing machines. Specifically, let L be a language accepted by a nondeterministic off-line Turing machine T. Let T have a t-symbol storage-tape alphabet. If for all but a fini

A note on the representation of finite t

A note on the representation of finite tree automata

✍ Wolfgang Reisig 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 237 KB

On the finite degree of ambiguity of fin

On the finite degree of ambiguity of finite tree automata

✍ Helmut Seidl 📂 Article 📅 1989 🏛 Springer-Verlag 🌐 English ⚖ 756 KB

The size of power automata

✍ K. Sutner 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 179 KB

We describe a class of simple transitive semiautomata that exhibit full exponential blow-up during deterministic simulation. For arbitrary semiautomata we show that it is PSPACE-complete to decide whether the size of the accessible part of their power automata exceeds a given bound. We comment on th