Wyniki wyszukiwania - BazTech

Ograniczanie wyników

3 Fundamenta Informaticae

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: two-way automata

Sortuj według:

Ogranicz wyniki do:

On the Length of Shortest Strings Accepted by Two-way Finite Automata

Dobronravov Egor, Dobronravov Nikita, Okhotin Alexander

Fundamenta Informaticae

2021

Vol. 180, nr 4

315--331

Given a two-way finite automaton recognizing a non-empty language, consider the length of the shortest string it accepts, and, for each n ≥ 1, let f(n) be the maximum of these lengths over all n-state automata. It is proved that for n-state two-way finite automata, whether deterministic or nondeterministic, this number is at least Ω(10n/5) and less than (2nn+1), with the lower bound reached over an alphabet of size Θ(n). Furthermore, for deterministic automata and for a fixed alphabet of size m ≥ 1, the length of the shortest string is at least e(1+o(1))√mn(log n− log m).

Two-way Automata and Regular Languages of Overlapping Tiles

Dicky A., Janin D.

Fundamenta Informaticae

2015

Vol. 141, nr 4

311--343

We consider classes of languages of overlapping tiles, i.e., subsets of the McAlister monoid: the class REG of languages definable by Kleene’s regular expressions, the class MSO of languages definable by formulas of monadic second-order logic, and the class REC of languages definable by morphisms into finite monoids. By extending the semantics of finite-state two-way automata (possibly with pebbles) from languages of words to languages of tiles, we obtain a complete characterization of the classes REG and MSO. In particular, we show that adding pebbles strictly increases the expressive power of two-way automata recognizing languages of tiles, but the hierarchy induced by the number of allowed pebbles collapses to level one.

State Complexity of Union and Intersection for Two-Way Nondeterministic Finite Automata

Kunc M., Okhotin A.

Fundamenta Informaticae

2011

Vol. 110, nr 1-4

231-239

The number of states in a two-way nondeterministic finite automaton (2NFA) needed to represent the intersection of languages given by an m-state 2NFA and an n-state 2NFA is shown to be at least m + n and at most m + n + 1. For the union operation, the number of states is exactly m + n. The lower bound is established for languages over a one-letter alphabet. The key point of the argument is the following number-theoretic lemma: for all m, n > 2 with m, n 6≈6 (and with finitely many other exceptions), there exist partitionsm = p1+. . .+pk and n = q1+. . .+ql, where all numbers p1, . . . , pk, q1, . . . , ql > 2 are powers of pairwise distinct primes. For completeness, an analogous statement about partitions of any two numbers m, n∉ {4, 6} (with a fewmore exceptions) into sums of pairwise distinct primes is established as well. Keywords: Finite automata, two-way automata, state complexity, partitions into sums of primes.