𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the descriptional complexity of finite automata with modified acceptance conditions

✍ Scribed by Markus Holzer; Martin Kutrib

Book ID
108280974
Publisher
Elsevier Science
Year
2005
Tongue
English
Weight
280 KB
Volume
330
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On the Computational Complexity of Finit
On the Computational Complexity of Finite Cellular Automata
✍ K. Sutner πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 932 KB

We study the computational complexity of several problems with the evolution of configurations on finite cellular automata. In many cases, the problems turn out to be complete in their respective classes. For example, the problem of deciding whether a configuration has a predecessor is shown to be N

On the complexity of intersecting finite
On the complexity of intersecting finite state automata and NL versus NP
✍ George Karakostas; Richard J. Lipton; Anastasios Viglas πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 256 KB

We consider uniform and non-uniform assumptions for the hardness of an explicit problem from ΓΏnite state automata theory. First we show that a small improvement in the known straightforward algorithm for this problem can be used to design faster algorithms for subset sum and factoring, and improved

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.