Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Vector Ambiguity and Freeness Problems in SL (2, Z)

Ko S.-K., Potapov I.

Fundamenta Informaticae

2018

Vol. 162, nr 2/3

161--182

We study the vector ambiguity problem and the vector freeness problem in SL (2, Z). Given a finitely generated n x n matrix semigroup S and an n-dimensional vector x, the vector ambiguity problem is to decide whether for every target vector y = Mx, where M ∈ S, M is unique. We also consider the vector freeness problem which is to show that every matrix M which is transforming x to Mx has a unique factorization with respect to the generator of S. We show that both problems are NP-complete in SL (2, Z), which is the set of 2 x 2 integer matrices with determinant 1. Moreover, we generalize the vector ambiguity problem and extend to the finite and k-vector ambiguity problems where we consider the degree of vector ambiguity of matrix semigroups.

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

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.