Name
Abstract | ||
|---|---|---|
We propose the one-way jumping finite automaton model, restricting the jumping relation of the recently introduced jumping finite automaton so that the machine can only jump over symbols it cannot process in its current state. The reading head of a one-way jumping finite automaton moves deterministically in one direction within the input word, whereas movement of the reading head of jumping finite automaton is non deterministic. The class of languages accepted by one-way jumping finite automata is different frorn that of jumping finite automata, in particular, it includes all regular languages, as opposed to the latter. We study one-way jumping finite automata and obtain closure properties, a pumping lemma, and separation results with respect to the classical language classes of the Chomsky hierarchy. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1142/S0129054116100165 | INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE |
Keywords | Field | DocType |
Jumping finite automata, pumping lemma, regular languages | Discrete mathematics,Quantum finite automata,Combinatorics,Two-way deterministic finite automaton,Deterministic automaton,Nondeterministic finite automaton,Deterministic finite automaton,Timed automaton,Mathematics,ω-automaton,Büchi automaton | Journal |
Volume | Issue | ISSN |
27 | 3 | 0129-0541 |
Citations | PageRank | References |
2 | 0.45 | 1 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hiroyuki Chigahara | 1 | 2 | 0.45 |
| Szilárd Zsolt Fazekas | 2 | 14 | 7.40 |
| Akihiro Yamamura | 3 | 96 | 13.29 |