Wyniki wyszukiwania - BazTech

1

Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers

Kutrib Martin, Malchers Andrea, Mereghetti Carlo, Palano Beatrice

Fundamenta Informaticae

|

2022

|

Vol. 185, nr 4

337--356

EN

An iterated uniform finite-state transducer (IUFST) runs the same length-preserving transduction, starting with a sweep on the input string and then iteratively sweeping on the output of the previous sweep. The IUFST accepts the input string by halting in an accepting state at the end of a sweep. We consider both the deterministic (IUFST) and nondeterministic (NIUFST) version of this device. We show that constant sweep bounded IUFSTs and NIUFSTs accept all and only regular languages. We study the state complexity of removing nondeterminism as well as sweeps on constant sweep bounded NIUFSTs, the descriptional power of constant sweep bounded IUFSTs and NIUFSTs with respect to classical models of finite-state automata, and the computational complexity of several decidability questions. Then, we focus on non-constant sweep bounded devices, proving the existence of a proper infinite nonregular language hierarchy depending on the sweep complexity both in the deterministic and nondeterministic case. Though NIUFSTs are "one-way" devices we show that they characterize the class of context-sensitive languages, that is, the complexity class DSpace (lin). Finally, we show that the nondeterministic devices are more powerful than their deterministic variant for a sublinear number of sweeps that is at least logarithmic.

2

Unambiguous Functions in Logarithmic Space

Herman G., Soltys M.

Fundamenta Informaticae

|

2012

|

Vol. 114, nr 2

129-147

EN

We investigate different variants of unambiguity in the context of computingmulti-valued functions. We propose a modification to the standard computation models of Turing machines and configuration graphs, which allows for unambiguity-preserving composition. We define a notion of reductions (based on function composition), which allows nondeterminism but controls its level of ambiguity. In light of this framework we establish reductions between different variants of path counting problems. We obtain improvements of results related to inductive counting.

3

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.

4

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

5

Nondeterminism in Constructive Z

Haghigh H., Mirian-Hosseinabadi S-H.

Fundamenta Informaticae

|

2008

|

Vol. 88, nr 1-2

109-134

EN

The abstraction inherent in most specifications and the need to specify nondeterministic programs are two well-known sources of nondeterminism in formal specifications. In this paper, we present a Z-based formalism by which one can specify bounded, unbounded, erratic, angelic, demonic, loose, strict, singular, and plural nondeterminism. To interpret our specifications, we use a constructive set theory, called CZ set theory, instead of the classical set theory Z. We have chosen CZ since it allows us to investigate the notion of nondeterminism from the formal program development point of view. In this way, we formally construct functional programs from Z specifications and then probe the effects of the initially specified nondeterminism on final programs. Our investigation shows that without specifying nondeterminism explicitly, the effects of the nondeterminism involved in initial specifications will not be preserved in final programs. We prove that using the new formalism, proposed by this paper, for writing nondeterministic specifications leads to programs that preserve the initially specified modalities of nondeterminism.

6

Computational Efficiency of Intermolecular Gene Assembly

Ishdorj T-O., Loos R., Petre I.

Fundamenta Informaticae

|

2008

|

Vol. 84, nr 3-4

363-373

EN

We investigate here the computational efficiency of gene rearrangement found in ciliates (unicellular organisms). We show how the so-called guided recombination systems, which model this gene rearrangement, can be used as problem solvers. Specifically, these systems can uniformly solve SAT with time complexity O(nźm) for a Boolean formula of m clauses over n variables.

7

On the Branching Complexity of P Systems

Ciobanu G., Paun G., Pérez-Jiménez M.J.

Fundamenta Informaticae

|

2006

|

Vol. 73, nr 1-2

27-36

EN

We consider two complexity parameters related to the graph of reachable configurations of a given P system, namely the outdegree as a measure of the degree of non-determinism, and the indegree as a measure of the degree of confluence. These parameters can be defined for both the generative and the accepting mode of using a P system. We investigate here these parameters in what concerns hierarchies and decidability issues. We prove that all hierarchies have only two levels and that all considered decidability problems have a negative answer.

8

On Interacting Automata with Limited Nondeterminism

Buchholz T., Klein A., Kutrib M.

Fundamenta Informaticae

|

2002

|

Vol. 52, nr 1-3

15-38

EN

One-way and two-way cellular language acceptors with restricted nondeterminism are investigated. The number of nondeterministic state transitions is regarded as limited resource which depends on the length of the input. We center our attention to real-time, linear-time and unrestricted-time computations. A speed-up result that allows any linear-time computation to be sped-up to real-time is proved. The relationships to deterministic arrays are considered. For an important subclass a characterization in terms of deterministic language families and e-free homomorphisms is given. Finally we prove strong closure properties of languages acceptable with a constant number of nondeterministic transitions.