✦ LIBER ✦

The finite graph problem for two-way alternating automata

✍ Scribed by Mikołaj Bojańczyk

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 206 KB
Volume: 298
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(02)00866-6

No coin nor oath required. For personal study only.

✦ Synopsis

Two-way alternating automata on inÿnite trees were introduced by Vardi (Reasoning about the part with two way

📜 SIMILAR VOLUMES

Optimal simulation of two-dimensional al

Optimal simulation of two-dimensional alternating finite automata by three-way nondeterministic Turing machines

✍ Akira Ito; Katsushi Inoue; Itsuo Takanami; Yue Wang 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 633 KB

The reachability problem for finite cell

The reachability problem for finite cellular automata

✍ Andrea Clementi; Russell Impagliazzo 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 474 KB

The equivalence problem for deterministi

The equivalence problem for deterministic two-tape automata

✍ Malcolm Bird 📂 Article 📅 1973 🏛 Elsevier Science 🌐 English ⚖ 715 KB

A decision procedure is described for equivalence of deterministic two-tape (oneway) automata. ## l. INTRODUCTION The notion of an n-tape (one-way, deterministic) automaton was introduced by Rabin and Scott [2]. Although the properties of these devices have been studied extensively, no answer has

The complexity of restricted regular exp

The complexity of restricted regular expressions and the synthesis problem for finite automata

✍ Ernst Leiss 📂 Article 📅 1981 🏛 Elsevier Science 🌐 English ⚖ 364 KB

Using hybrid metaheuristics for the one-

Using hybrid metaheuristics for the one-way and two-way network design problem

✍ Zvi Drezner; Said Salhi 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 211 KB

A note on the space complexity of some d

A note on the space complexity of some decision problems for finite automata

✍ Tao Jiang; B. Ravikumar 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 533 KB

In this note, we establish the space complexity of decision problems (such as membership, nonemptiness and equivalence) for some finite automata. Our study includes 2-way infinite automata with a pebble.