Wyniki wyszukiwania - BazTech

1

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

EN

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).

2

Fault diagnosis in nonlinear hybrid systems

Zhirabok A., Shumsky A.

International Journal of Applied Mathematics and Computer Science

|

2018

|

Vol. 28, no. 4

635--648

EN

The problem of fault diagnosis in hybrid systems is investigated. It is assumed that the hybrid systems under consideration consist of a finite automaton, a set of nonlinear difference equations and the so-called mode activator that coordinates the action of the other two parts. To solve the fault diagnosis problem, hybrid residual generators based on both diagnostic observers and parity relations are used. It is shown that the hybrid nature of the system imposes some restrictions on the possibility of creating such generators. Sufficient solvability conditions of the fault diagnosis problem are found. Examples illustrate details of the solution.

3

Zestawienie i porównanie automatów probabilistycznych i kwantowych

Siedlecka-Lamch O.

Studia i Materiały / Europejska Uczelnia Informatyczno-Ekonomiczna w Warszawie

|

2017

|

Nr 1(13)

77--83

PL

Większość systemów informatycznych można modelować z wykorzystaniem różnego rodzaju automatów skończonych: deterministycznych, niedeterministycznych, probabilistycznych itp. Automaty te można badać pod kątem osiągalności określonych stanów i dzięki temu sprawdzać, czy system może znaleźć się w stanie krytycznym, błędnym, niechcianym. Mamy również możliwość dokonania operacji minimalizacji automatów. Praktycznie ogranicza się to do znalezienia stanów nadmiarowych i nieosiągalnych – dzięki czemu mamy również sposobność zminimalizować oryginalny, modelowany system, zaoszczędzić na dokonywanych operacjach, pamięci, a nawet sprzęcie.

EN

Most IT systems can be modeled with the use of various types of finite automata: deterministic, non-deterministic, probabilistic, etc. These automatons can be tested for reachability of certain states and thus we can check whether the system can be in a critical, erroneous or unwanted state. We also have the ability to perform the operation of automata minimization. Practically, this is limited to finding redundant and unreachable states – so we also have the opportunity to minimize the original, modeled system, save on operations amount, memory, and even hardware.

4

Tight Bounds for Cut-Operations on Deterministic Finite Automata

Drewes F., van der Merwe B., Holzer M., Jakobi S.

Fundamenta Informaticae

|

2017

|

Vol. 155, nr 1/2

89--110

EN

We investigate the state complexity of the cut and iterated cut operation for deterministic finite automata (DFAs), answering an open question stated in [M. BERGLUND, et al.: Cuts in regular expressions. In Proc. DLT, LNCS 7907, 2011]. These operations can be seen as an alternative to ordinary concatenation and Kleene star modelling leftmost maximal string matching. We show that the cut operation has a matching upper and lower bound of n states, if m = 1, and (n-1).m+n states, otherwise, on DFAs accepting the cut of two individual languages that are accepted by n-andm-state DFAs, respectively. In the unary case we obtain max(2n-1;m+n-2) states as a tight bound--notice that for m ≤n the bound for unary DFAs only depends on the former automaton and not on the latter. For accepting the iterated cut of a language accepted by an n-state DFA we find a matching bound of 1+(n+1). F( 1; n+2;-n+2; n+1 j-1 ) states on DFAs, if n ≥ 4 and where F refers to the generalized hypergeometric function. This bound is in the order of magnitude Θ((n - 1)!). Finally, the bound drops to 2n - 1 for unary DFAs accepting the iterated cut of an n-state DFA, if n ≥ 3, and thus is similar to the bound for the cut operation on unary DFAs.

5

State Complexity of Basic Operations on Non-Returning Regular Languages

Eom H.-S., Han Y.-S., Jirásková G.

Fundamenta Informaticae

|

2016

|

Vol. 144, nr 2

161--182

EN

We consider the state complexity of basic operations on non-returning regular languages. For a non-returning minimal DFA, the start state does not have any in-transitions. We establish the precise state complexity of four Boolean operations (union, intersection, difference, symmetric difference), catenation, reverse, and Kleene-star for non-returning regular languages. Our results are usually smaller than the state complexities for general regular languages and larger than the state complexities for suffix-free regular languages. In the case of catenation and reversal, we define witness languages over a ternary alphabet. Then we provide lower bounds for a binary alphabet. For every operation, we also study the unary case.

6

Limited Automata and Context-Free Languages

Pighizzini G., Pisoni A.

Fundamenta Informaticae

|

2015

|

Vol. 136, nr 1/2

157--176

EN

Limited automata are one-tape Turing machines which are allowed to rewrite each tape cell only in the first d visits, for a given constant d. For each d ≥ 2, these devices characterize the class of context-free languages. We investigate the equivalence between 2-limited automata and pushdown automata, comparing the relative sizes of their descriptions. We prove exponential upper and lower bounds for the sizes of pushdown automata simulating 2-limited automata. In the case of the conversion of deterministic 2-limited automata into deterministic pushdown automata the upper bound is double exponential and we conjecture that it cannot be reduced. On the other hand, from pushdown automata we can obtain equivalent 2-limited automata of polynomial size, also preserving determinism. From our results, it follows that the class of languages accepted by deterministic 2- limited automata coincides with the class of deterministic context-free languages.

7

Finite Automata with Multiset Memory : A New Characterization of Chomsky Hierarchy

Okubo F., Yokomori T.

Fundamenta Informaticae

|

2015

|

Vol. 138, nr 1/2

331--44

EN

This paper concerns new characterizations of language classes in the Chomsky hierarchy in terms of a new type of computing device called FAMM (Finite Automaton with Multiset Memory) in which a multiset of symbol objects is available for the storage of working space. Unlike the stack or the tape for a storage, the multiset might seem to be less powerful in computing task, due to the lack of positional (structural) information of stored data. We introduce the class of FAMMs of degree d (for non-negative integer d) in general form, and investigate the computing powers of some subclasses of those FAMMs. We show that the classes of languages accepted by FAMMs of degree 0, by FAMMs of degree 1, by exponentially-boundedFAMMs of degree 2, and by FAMMs of degree 2 are exactly the four classes of languages REG, CF, CS and RE in the Chomsky hierarchy, respectively. Thus, this unified view from multiset-based computing provides new insight into the computational aspects of the Chomsky hierarchy.

8

State Complexity of Combined Operations with Union, Intersection, Star and Reversal

Gao Y., Yu S

Fundamenta Informaticae

|

2012

|

Vol. 116, nr 1-4

79-92

EN

In this paper, we study the state complexities of four combined operations: [formula]. The tight bounds for all these combined operations on regular languages are obtained and proved. We show that, as usual, they are different from the mathematical compositions of the state complexities of their individual participating operations.

9

A Note on the Logical Definability of Rational Trace Languages

Choffrut C.

Fundamenta Informaticae

|

2012

|

Vol. 116, nr 1-4

45-50

EN

The regular languages in the free monoid generated by a finite alphabet A are exactly the languages that are the models of some sentence of the second-order monadic logic of one successor and a unary predicate for each letter. For trace monoids the natural extension obtained by adapting the successor to the partial order underlying the traces is insufficient to capture the family of their rational subsets. We show that these subsets can be expressed by formulas of the form ∃Γφ where φ is a first-order formula over the structure of traces and Γ is an n-ary predicate semantically restricted, where n is the cardinality of the alphabet.

10

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

EN

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.

11

Rough Approximations in Varieties of Regular Languages

Martin G., Steinby M.

Fundamenta Informaticae

|

2011

|

Vol. 112, nr 4

281-303

EN

We study approximations of regular languages bymembers of a given variety L of regular languages. These are upper or lower approximations in the sense of Pawlak’s rough set theory with respect to congruences belonging to the variety of congruences corresponding to L. In particular, we consider the closest upper and lower approximations in L. In so-called principal varieties these always exist, and we present algorithms for finding them, but for other varieties the situation is more complex. Although we consider just Eilenberg’s +-varieties, the general ideas apply also to other types of varieties of languages. Our work may also be viewed as an approach to the characterizable inference problem in which a language of a certain kind is to be inferred from a given sample.

12

On the State Complexity of Star of Union and Star of Intersection

Jiraskova G., Okhotin A.

Fundamenta Informaticae

|

2011

|

Vol. 109, nr 2

161-178

EN

The state complexity of the star of union of anm-state DFA language and an n-state DFA language is proved to be 2m+n-1 - 2m-1 - 2n-1 +1 for every alphabet of at least two letters. The state complexity of the star of intersection is established as [...} for every alphabet of six or more letters. This improves the recent results of A. Salomaa, K. Salomaa and Yu ("State complexity of combined operations", Theoret. Comput. Sci., 383 (2007) 140–152).

13

On Approximating Non-regular Languages by Regular Languages

Eisman G., Ravikumar B.

Fundamenta Informaticae

|

2011

|

Vol. 110, nr 1-4

125-142

EN

Approximate computation is a central concept in algorithms and computation theory. Our notion of approximation is that the algorithm performs correctly on most of the inputs. We propose some finite automata models to study the question of how well a finite automaton can approximately recognize a non-regular language. On the one hand, we show that there are natural problems for which a DFA can correctly solve almost all the instances, but not all instances. An example of such a problem is a decision question about the number of digits in the square of a given integer. On the other hand, we show that some languages (such as L_majority = {x ∈(0 + 1)* | x has more 1’s than 0’s }) can’t be approximated by any regular language in a strong sense. We also show that there are problems that are intermediate (between the extremes stated above) in terms of how we well a regular language can approximate it. An example of such a problem is a decision question about the number of digits in the product of two integers. We also present results comparing different models of approximation.

14

Critical resources software and control modeling with finite automata

Schreyer B., Kosiński K.

Theoretical and Applied Informatics

|

2010

|

Vol. 22, No. 3

155-163

EN

There are analogies between modeling the transportation systems with critical resources (CR) and a critical section (CS) problem in operating systems. This article is developing this analogy in the direction of using the finite automata. The article analyses Peterson’s algorithm [4], [5] and Lamport’s algorithm [2] using deterministic finite automata (DFA) as well as it takes into consideration the problem of modeling traffic with binary semaphore using nondeterministic finite automata (NFA). Introduction of finite automata makes traffic control modeling much clearer on programming side and brings hardware application closer to such control.

PL

Problem poruszany w artykule dotyczy modelowania ruchu w systemie transportowym ze środkami krytycznymi (CR). Jest oparta na analogii z podobnym problemem sekcji krytycznej (CS) w systemach operacyjnych. Niniejszy artykuł jest rozwinięciem tej idei w naturalnym kierunku uogólnienia tj. z zastosowaniem automatów skończonych. Artykuł analizuje algorytm Petersona oraz algorytm Lamporta przy użyciu deterministycznych automatów skończonych, jak również problem modelowania ruchu przy pomocy semaforu binarnego przy użyciu niedeterministycznych automatów skończonych. Wprowadzenie automatów skończonych czyni modelowanie sterowania ruchem na drodze programowej bardziej przejrzystym jak również przybliża zastosowanie hardwaru do tego sterowania. W artykule dokonano analizy trzech algorytmów krytycznej sekcji w systemach operacyjnych w zastosowaniu do sterowania jednostkami transportowymi w kontroli przyznawania środków krytycznych. W analizie zastosowano skończone automaty deterministyczne oraz niedeterministyczne. Jak wynika z tej analizy, wszystkie trzy warunki (1) poprawnej kontroli JT zostały spełnione. Jednocześnie automaty skończone pozwoliły na zwarte i przejrzyste modelowanie problemu CR w systemach transportowych.

15

On the State Complexity of Scattered Substrings and Superstrings

Okhotin A.

Fundamenta Informaticae

|

2010

|

Vol. 99, nr 3

325-338

EN

It is proved that the set of scattered substrings of a language recognized by an n-state DFA requires a DFA with at least [formula] states (the known upper bound is 2*n), with witness languages given over an exponentially growing alphabet. For a 3-letter alphabet, scattered substrings are shown to require at least [formula] states. A similar state complexity function for scattered superstrings is determined to be exactly 2*(n-2) + 1 for an alphabet of at least n -2 letters, and strictly less for any smaller alphabet. For a 3-letter alphabet, the state complexity of scattered superstrings is at least [formula]

16

Petri Net Controlled Finite Automata

Farwer B., Jantzen M., Kudlek M., Rölke H., Zetzsche G.

Fundamenta Informaticae

|

2008

|

Vol. 85, nr 1-4

111-121

EN

We present a generalization of finite automata using Petri nets as control, called Concurrent Finite Automata for short. Several modes of acceptance, defined by final markings of the Petri net, are introduced, and their equivalence is shown. The class of languages obtained by l-free concurrent finite automata contains both the class of regular sets and the class of Petri net languages defined by final marking, and is contained in the class of context-sensitive languages.

17

Language Classes Defined by Concurrent Finite Automata

Jantzen M., Kudlek M., Zetzsche G.

Fundamenta Informaticae

|

2008

|

Vol. 85, nr 1-4

267-280

EN

This paper presents results regarding the various relations among the language classes defined by Concurrent Finite Automata, relations to other language classes, as well as decidability and closure properties.

18

Complexity of Topological Properties of Regular w-Languages

Selivanov V.L., Wagner K.W.

Fundamenta Informaticae

|

2008

|

Vol. 83, nr 1-2

197-217

EN

We determine the complexity of topological properties (i.e., properties closed under the Wadge equivalence) of regular w-languages by showing that they are typically NL-complete (PSPACE-complete) for the deterministic Muller, Mostowski and Büchi automata (respectively, for the nondeterministic Rabin, Muller, Mostowski and Büchi automata). For the deterministic Rabin and Streett automata and for the nondeterministic Streett automata upper and lower complexity bounds for the topological properties are established.

19

Star-Connected Flat Languages and Automata

Klunder B.

Fundamenta Informaticae

|

2006

|

Vol. 72, nr 1-3

235-243

EN

Star-connected rational expressions were considered only as expressions defining trace languages. In this paper we continue the study of the class of flat languages defined by this kind of rational expressions. We strengthen results of [4] and prove that any star-connected language has an automaton with cycles which are composition of connected cycles. This condition is sufficient for star-connected languages provided that the dependency relation is transitive. As a consequence we obtain for every alphabet stronger pumping lemma for star-connected languages. Finally, the product of two automata inherits this property from the components and thus for alphabet with transitive dependency relation the set of all star-connected languages is closed under intersections.

20

Automata Recognizing No Words : A Statistical Approach

Calude C.S., Campeanu C., Dumitrescu M.

Fundamenta Informaticae

|

2006

|

Vol. 73, nr 1-2

1-18

EN

How likely is that a randomly given (non-) deterministic finite automaton recognizes no word? A quick reflection seems to indicate that not too many finite automata accept no word; but, can this intuition be confirmed? In this paper we offer a statistical approach which allows us to conclude that for automata, with a large enough number of states, the probability that a given (non-) deterministic finite automaton recognizes no word is close to zero. More precisely, we will show, with a high degree of accuracy (i.e., with precision higher than 99% and level of confidence 0.9973), that for both deterministic and non-deterministic finite automata: a) the probability that an automaton recognizes no word tends to zero when the number of states and the number of letters in the alphabet tend to infinity, b) if the number of states is fixed and rather small, then even if the number of letters of the alphabet of the automaton tends to infinity, the probability is strictly positive. The result a) is obtained via a statistical analysis; for b) we use a combinatorial and statistical analysis. The present analysis shows that for all practical purposes the fraction of automata recognizing no words tends to zero when the number of states and the number of letters in the alphabet grow indefinitely. From a theoretical point of view, the result can motivate the search for ``certitude'', that is, a proof of the fact established here in probabilistic terms. In the last section we critically discuss the result and the method used in this paper.