PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 16

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  state complexity
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote 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
Content available How to embed noncrossing trees in Universal Dependencies treebanks in a low-complexity regular language
Yli-Jyrä Anssi Mikael
Journal of Language Modelling
|
2019
|
Vol. 7, No. 2
177--232
EN
A recently proposed balanced-bracket encoding (Yli-Jyrä and Gómez-Rodríguez 2017) has given us a way to embed all noncrossing dependency graphs into the string space and to formulate their exact arcfactored inference problem (Kuhlmann and Johnsson 2015) as the best string problem in a dynamically constructed and weighted unambiguous context-free grammar. The current work improves the encoding and makes it shallower by omitting redundant brackets from it. The streamlined encoding gives rise to a bounded-depth subset approximation that is represented by a small finite-state automaton. When bounded to 7 levels of balanced brackets, the automaton has 762 states and represents a strict superset of more than 99.9999% of the noncrossing trees available in Universal Dependencies 2.4 (Nivre et al. 2019). In addition, it strictly contains all 15-vertex noncrossing digraphs. When bounded to 4 levels and 90 states, the automaton still captures 99.2% of all noncrossing trees in the reference dataset. The approach is flexible and extensible towards unrestricted graphs, and it suggests tight finite-state bounds for dependency parsing, and for the main existing parsing methods.
3
Content available remote State Complexity of k-Parallel Tree Concatenation
Han Y.-S., Ko S.-K., Salomaa K.
Fundamenta Informaticae
|
2017
|
Vol. 154, nr 1/4
185--199
EN
We give an optimized construction of a tree automaton recognizing the k-parallel, k ≥ 1, tree concatenation of two regular tree languages. For tree automata with m and n states, respectively, the construction yields an upper bound (m+1/2)(n+1)⋅2nk−1 for the state complexity of k-parallel tree concatenation. We give a matching lower bound in the case k = 2. We conjecture that the upper bound is tight for all values of k. We also consider the special case where one of the tree languages is the set of all ranked trees and in this case establish a different tight state complexity bound for all values of k.
4
Content available remote 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.
5
Content available remote Distinguishability Operations and Closures
Câmpeanu C., Moreira N., Reis R.
Fundamenta Informaticae
|
2016
|
Vol. 148, nr 3/4
243--266
EN
Given a language L, we study the language of words D(L), that distinguish between pairs of different left quotients of L. We characterize this distinguishability operation, show that its iteration has always a fixed point, and we generalize this result to operations derived from closure operators and Boolean operators. For the case of regular languages, we give an upper bound for the state complexity of the distinguishability operation, and prove its tightness. We show that the set of minimal words that can be used to distinguish between different left quotients of a regular language L has at most n - 1 elements, where n is the state complexity of L, and we also study the properties of its iteration. We generalize the results for the languages of words that distinguish between pairs of different right quotients and two-sided quotients of a language L.
6
Content available remote Filtrations of Formal Languages by Arithmetic Progressions
Mousavi H., Shallit J.
Fundamenta Informaticae
|
2013
|
Vol. 123, nr 2
135--142
EN
A filtration of a formal language L by a sequence s maps L to the set of words formed by taking the letters of words of L indexed only by s. We consider the languages resulting from filtering by all arithmetic progressions. If L is regular, it is easy to see that only finitely many distinct languages result; we give bounds on the number of distinct languages in terms of the state complexity of L. By contrast, there exist CFL’s that give infinitely many distinct languages as a result. We use our technique to show that two related operations, including diag (which extracts the diagonal of words of square length arranged in a square array), preserve regularity but do not preserve context-freeness.
7
Content available remote 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.
8
Content available remote Mirror Images and Schemes for the Maximal Complexity of Nondeterminism
Salomaa A.
Fundamenta Informaticae
|
2012
|
Vol. 116, nr 1-4
237-249
EN
We present schemes of deterministic finite automata such that, for every nontrivial automaton A resulting from the scheme with n states, the state complexity of the mirror image of the language L(A) equals 2n. The construction leads to cases, where the increase in complexity is maximal in the transition from nondeterministic devices to deterministic ones. We also discuss the crucial importance of the size of the alphabet and present some open problems.
9
Content available remote Transformations Between Different Models of Unranked Bottom-Up Tree Automata
Piao X., Salomaa K.
Fundamenta Informaticae
|
2011
|
Vol. 109, nr 4
405-424
EN
We consider the representational state complexity of unranked tree automata. The bottomup computation of an unranked tree automaton may be either deterministic or nondeterministic, and further variants arise depending on whether the horizontal string languages defining the transitions are represented by a DFA or an NFA. Also, we consider for unranked tree automata the alternative syntactic definition of determinism introduced by Cristau et al. (FCT’05, LNCS 3623, pp. 68–79). We establish upper and lower bounds for the state complexity of conversions between different types of unranked tree automata
10
Content available remote 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
Content available remote 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).
12
Content available remote On Networks of Evolutionary Processors with Filters Accepted by Two-State-Automata
Dassow J., Truthe B.
Fundamenta Informaticae
|
2011
|
Vol. 112, nr 2/3
157-170
EN
In this paper, we study networks of evolutionary processors where the filters are chosen as special regular sets. We consider networks where all the filters belong to a set of languages that are accepted by deterministic finite automata with a fixed number of states. We show that if the number of states is bounded by two, then every recursively enumerable language can be generated by such a network. If the number of states is bounded by one, then not all regular languages but non-context-free languages can be generated.
13
Content available remote 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]
14
Content available remote The State Complexity of Two Combined Operations: Star of Catenation and Star of Reversal
Gao Y., Salomaa K., Yu S
Fundamenta Informaticae
|
2008
|
Vol. 83, nr 1-2
75-89
EN
The state complexity of two combined operations, star of catenation and star of reversal, on regular languages is considered in this paper. Tight bounds are obtained for both combined operations. The results clearly show that the state complexity of a combined operation can be very different from the composition of the state complexities of its participating individual operations. A new approach for research in automata and formal language theory is also explained.
15
Content available remote State Complexity : Recent Results and Open Problems
Yu S
Fundamenta Informaticae
|
2005
|
Vol. 64, nr 1-4
471-480
EN
In this paper, we summarize recent results and progress in state complexity research. We analyze why many basic state complexity problems were not solved earlier, in the sixties and seventies. We also suggest several future directions for this area of research.
16
Content available remote Results on Transforming NFA into DFCA
Câmpeanu C., Kari L., Păun A.
Fundamenta Informaticae
|
2005
|
Vol. 64, nr 1-4
53-63
EN
In this paper we consider the transformation from (minimal) non-deterministic finite automata (NFAs) to deterministic finite cover automata (DFCAs). We want to compare the two equivalent accepting devices with respect to their number of states; this becomes in fact a comparison between the expression power of the nondeterministic device and the expression power of the deterministic with loops device. We prove a lower bound for the maximum state complexity of deterministic finite cover automata obtained from non-deterministic finite automata of a given state complexity n, considering the case of a binary alphabet. We show, for such binary alphabets, that the difference between maximum blow-up state complexity of DFA and DFCA can be as small as [..]compared to the number of states of the minimal DFA. Moreover, we show the structure of automata for worst case exponential blow-up complexity from NFA to DFCA. We conjecture that the lower bound given in the paper is also the upper bound. Several results clarifying some of the structure of the automata in the worst case are given (we strongly believe they will be pivotal in the upper bound proof).
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.