PL
 |
EN
Nowa wersja platformy, zawierająca wyłącznie zasoby pełnotekstowe, jest już dostępna.
Przejdź na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 10

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

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote On the State Complexity of Scattered Substrings and Superstrings
100%
Okhotin A.
Fundamenta Informaticae
|
2010
|
tom 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]
2
Content available remote Language Equations with Symmetric Difference
100%
Okhotin A.
Fundamenta Informaticae
|
2012
|
tom Vol. 116, nr 1-4
205-222
EN
The paper investigates the expressive power of language equations with the operations of concatenation and symmetric difference. For equations over every finite alphabet Σ with |Σ| ≥1, it is demonstrated that the sets representable by unique solutions of such equations are exactly the recursive sets over , and the sets representable by their least (greatest) solutions are exactly the recursively enumerable sets (their complements, respectively). If |Σ| ≥ 2, the same characterization holds already for equations using symmetric difference and linear concatenation with regular constants. In both cases, the solution existence problem is Π (0,1)-complete, the existence of a unique, a least or a greatest solution is Π(0,2)-complete, while the existence of finitely many solutions is Σ(0,3)-complete.
3
Content available remote Computational Universality in One-variable Language Equations
100%
Okhotin A.
Fundamenta Informaticae
|
2006
|
tom Vol. 74, nr 4
563-578
EN
It has recently been shown that several computational models, such as trellis automata, recursive functions and Turing machines, admit characterization by resolved systems of language equations with different sets of language-theoretic operations. This paper investigates how simple the systems of equations from the computationally universal types could be while still retaining their universality. It is proved that the universality and the associated hardness of decision problems begins at one-variable equations. Additionally, it is shown that language equations with added quotient with regular languages can specify every set representable in first-order Peano arithmetic.
4
Content available remote State Complexity of Union and Intersection for Two-Way Nondeterministic Finite Automata
63%
Kunc M. , Okhotin A.
Fundamenta Informaticae
|
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
Content available remote On the Number of Nonterminal Symbols in Unambiguous Conjunctive Grammars
63%
Jeż A. , Okhotin A.
Fundamenta Informaticae
|
2018
|
tom Vol. 162, nr 1
43--72
EN
Unambiguous conjunctive grammars with 1 nonterminal symbol are shown to be strictly weaker than the grammars with 2 nonterminal symbols, which are in turn strictly weaker that the grammars with 3 or more nonterminal symbols. This hierarchy is established by considering grammars over a one-symbol alphabet, for which it is shown that 1-nonterminal grammars describe only regular languages, 2-nonterminal grammars describe some non-regular languages, but all of them are in a certain sense sparse, whereas 3-nonterminal grammars may describe some non-regular languages of non-zero density. It is also proved that one can test a 2-nonterminal grammar for equivalence with a regular language, whereas the equivalence between a pair of 2-nonterminal grammars is undecidable.
6
Content available remote Univariate Equations Over Sets of Natural Numbers
63%
Jeż A. , Okhotin A.
Fundamenta Informaticae
|
2010
|
tom Vol. 104, nr 4
329-348
EN
It is shown that equations of the form φ(X) = ψ(X), in which the unknown X is a set of natural numbers and φ, ψ use the operations of union, intersection and addition of sets S + T = {m + n | m ∈ S, n ∈T}, can simulate systems of equations φ(X1, . . . ,Xn) = φ(X1, . . . ,Xn) with 1 ≤ j ≤ l, in the sense that solutions of any such system are encoded in the solutions of the corresponding equation. This implies computational universality of least and greatest solutions of equations φ(X) = ψ(X), as well as undecidability of their basic decision problems. It is sufficient to use only singleton constants in the construction. All results equally apply to language equations over a one-letter alphabet Σ = {α}.
7
Content available remote On the State Complexity of Star of Union and Star of Intersection
63%
Jiraskova G. , Okhotin A.
Fundamenta Informaticae
|
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).
8
Content available remote Contextual Grammars with Uniform Sets of Trajectories
63%
Okhotin A. , Salomaa K.
Fundamenta Informaticae
|
2005
|
tom Vol. 64, nr 1-4
341-351
EN
A uniform contextual grammar with contexts shuffled along trajectories uses the same set of trajectories for each context. We prove that when the alphabet has at least two symbols, the non-uniform contextual grammars with trajectories are strictly more powerful than the uniform variant. For unary alphabets the generative power of the two variants coincides, and the same is true for grammars where the sets of trajectories are regular or context-free.
9
Content available remote On Language Equations with One-sided Concatenation
63%
Baader F. , Okhotin A.
Fundamenta Informaticae
|
2013
|
tom Vol. 126, nr 1
1--35
EN
Language equations are equations where both the constants occurring in the equations and the solutions are formal languages. They have first been introduced in formal language theory, but are now also considered in other areas of computer science. In the present paper, we restrict the attention to language equations with one-sided concatenation, but in contrast to previous work on these equations, we allow not just union but all Boolean operations to be used when formulating them. In addition, we are not just interested in deciding solvability of such equations, but also in deciding other properties of the set of solutions, like its cardinality (finite, infinite, uncountable) and whether it contains least/greatest solutions. We show that all these decision problems are EXPTIME-complete.
10
Content available remote One-Visit Caterpillar Tree Automata
51%
Okhotin A. , Salomaa K. , Domaratzki M.
Fundamenta Informaticae
|
2002
|
tom Vol. 52, nr 4
361-375
EN
We study caterpillar tree automata [3] that are restricted to enter any subtree at most one time (or k times). We show that, somewhat surprisingly, the deterministic one-visit automata can already, for instance, evaluate trees where the nodes represent some non-associative operations. We show that there exist regular tree languages that cannot be accepted by a one-visit automaton, thus proving a weakened form of a conjecture of Brüggemann-Klein and Wood [3]. We establish that the k-visit property is decidable.
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ć.