Wyniki wyszukiwania - Biblioteka Nauki

1

Petri Net Controlled Finite Automata

100%

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

|

2008

|

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

2

Complexity of Topological Properties of Regular w-Languages

100%

Selivanov V. L. , Wagner K. W.

|

2008

|

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

3

On Approximating Non-regular Languages by Regular Languages

80%

Eisman G. , Ravikumar B.

|

2011

|

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

4

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

80%

Kunc M. , Okhotin A.

|

2011

|

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

5

Tight Bounds for Cut-Operations on Deterministic Finite Automata

80%

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

Fundamenta Informaticae

|

2017

|

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

6

A relation between unambiguous regular expressions and abstract data types

80%

Preoteasa V.

|

1999

|

tom Vol. 40, Nr 1

53-77

EN

Using a categorical model of abstract data types [2,3,13,15], we show, following the Kozen's technique [10] and Tarjan's constructions for a deterministic automaton [16], that if two unambiguous regular expressions define the same regular language, then they represent two isomorphic abstract data types.

7

On Star-Connected Flat Languages

80%

Klunder B. , Ochmański E. , Stawikowska K.

|

tom Vol. 67, nr 1-3

93--105

EN

Up to now, star-connected rational expressions were considered only as expressions defining trace languages. In this paper we study the class of flat languages defined by this kind of rational expressions. We consider regular languages inducing recognizable trace languages and its subclasses: languages of finite ranks and star-connected languages. Main results are the following: rank of any star-connected language is finite; any star-connected language has an automaton with connected simple cycles; two pumping lemmas for star-connected languages. Moreover, we show that none of the investigated classes is closed under complement and that the class of languages of finite ranks is not closed under intersection. Finally, we briefly mention some decision problems and formulate several open questions.

8

Language Classes Defined by Concurrent Finite Automata

80%

Jantzen M. , Kudlek M. , Zetzsche G.

|

2008

|

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

9

Communication complexity for multi-speed cooperating automata

80%

Jurdziński T. , Kutyłowski M. , Rzechonek P. , Zatopiański J.

|

tom Vol. 24, nr 3

17-30

EN

We consider bounded memory asynchronous systems. They consist of finite automata working independently and communicating by exchanging messages. We discuss what impact the differences in timing models on computational power of such systems have. It is known that a total lack of synchronization has profound consequences for computational power of systems of automata. Lower bounds found for this model indicate that the only way to perform a nontrivial computation would be to re-synchronize the automata every 0(1) steps. We examine much weaker form of asynchronism. We consider the model in which automata work with constant speeds, but the speed might be different for each automaton, and the automata have no knowledge about the speeds. (We call this model multi-speed systems of finite automata.) In particular, it may happen that some speed cannot be expressed exactly by the means of internal states of automata. Nevertheless, we expect the automata to compute the correct output. The main result of this paper is that, quite unexpectedly, the systems described might be as powerful as synchronous systems, where all automata work with the same speed. More precisely, some languages, which have been candidates for distinguishing multi-speed and synchronous models, can be recognized by multi-speed systems with approximately the same number of messages sent.

10

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

80%

Dobronravov E. , Dobronravov N. , Okhotin A.

Fundamenta Informaticae

|

2021

|

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

11

A Note on the Logical Definability of Rational Trace Languages

80%

Choffrut C.

|

2012

|

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

12

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

80%

Gao Y. , Yu S.

|

2012

|

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

13

Rough Approximations in Varieties of Regular Languages

80%

Martin G. , Steinby M.

|

2011

|

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

14

State Complexity of Basic Operations on Non-Returning Regular Languages

80%

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

Fundamenta Informaticae

|

2016

|

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

15

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

80%

Okubo F. , Yokomori T.

Fundamenta Informaticae

|

2015

|

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

16

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

80%

Jiraskova G. , Okhotin A.

|

2011

|

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

17

From Mirkin's prebases to Antimirov's world partial derivatives

80%

Champarnaud J.-M. , Ziadi D.

|

2001

|

tom Vol. 45, nr 3

195-205

EN

Our aim is to give a proof of the fact that two notions related to regular expressions, the prebases due to Mirkin and the partial derivatives introduced by Antimirov lead to the construction of identical nondeterministic automata recognizing the language of a given regular expression.

18

Star-Connected Flat Languages and Automata

80%

Klunder B.

|

2006

|

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

19

Automata Recognizing No Words : A Statistical Approach

80%

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

|

2006

|

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

20

New Iteration Lemmata for Regular Languages

80%

Dömösi P. , Kudlek M.

|

2005

|

tom Vol. 64, nr 1-4

151-157

EN

Using well-known characterizations of regular languages, on the basis of known iteration lemmas, new iteration lemmas for regular languages are given.