𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the average state and transition complexity of finite languages

✍ Scribed by Hermann Gruber; Markus Holzer

Book ID
108281350
Publisher
Elsevier Science
Year
2007
Tongue
English
Weight
312 KB
Volume
387
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On the context-free production complexit
On the context-free production complexity of finite languages
✍ Zsolt Tuza πŸ“‚ Article πŸ“… 1987 πŸ› Elsevier Science 🌐 English βš– 696 KB

The following problem is investigated. Let L be a given finite language, LcL,= {ub: I ~o,bsn, of/~}. Determine the minimal natural number c(L) such that L can be generated by c(L) context-free productions. Among others, max c(L) = O(n'/log n) is proved, and languages satisfying c(L) = IL) are charac

The complexity of countable categoricity
The complexity of countable categoricity in finite languages
✍ Aleksander Ivanov πŸ“‚ Article πŸ“… 2011 πŸ› John Wiley and Sons 🌐 English βš– 139 KB

## Abstract We study complexity of the index set of countably categorical theories and Ehrenfeucht theories in finite languages.

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

Bounds on the complexity of recurrent ne
Bounds on the complexity of recurrent neural network implementations of finite state machines
✍ Bill G. Horne; Don R. Hush πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 823 KB

In this paper the efficiency of recurrent neural network implementations of m-state finite state machines will be explored. Specifically, it will be shown that the node complexity for the unrestricted case can be bounded above by O(v/-m-). It will also be shown that the node complexity is 0( ~) when