Wyniki wyszukiwania - BazTech

1

A Shift-free Characterization of NP within Interval-valued Computing

Nagy B., Vályi S.

Fundamenta Informaticae

|

2017

|

Vol. 155, nr 1/2

187--207

EN

Interval-valued computing is a new computing paradigm that is based on manipulations of interval-values. Interval-values are finite unions of intervals on the unit interval [0; 1) so this kind of computing can be considered as a continuous space machine like optical computing [25]. Based on the massive parallelism of this paradigm, various intractable problems can be solved efficiently, i.e., by polynomial number of steps. In this paper, the well-known complexity classes, NP and coNP are addressed. A specific subclass of polynomial size interval-valued computations is proven to characterize NP, that is, exactly languages with non-deterministically polynomial time complexity can be decided by interval-valued computations of this subclass. This specific subclass of interval-valued computations does not use any of the shift operators, moreover the product operator is used only in the starting section of the computation. Due to the fact that interval-valued computing is a deterministic model of computing, an analogue result can be established for the class coNP.

2

Dense Projection Tomography on the Triangular Tiling

Nagy B., Lukić T.

Fundamenta Informaticae

|

2016

|

Vol. 145, nr 2

125--141

EN

In this paper, we consider the binary tomography reconstruction problem. A new approach is proposed what exploits a possibility provided by the natural structure of the triangular grid, which is not available in the case of the classical square grid. In contrast to the square grid, in the case of the triangular grid information need for the reconstruction of the unknown image is increasing when not only one, but two projections are used by lanes. In this way, the number of Δ and ∇ shaped pixels per lane can be determined. We propose this type of projection approach and call it dense projections. The reconstruction is based on three projection directions by the lane directions of the grid (they are analogous to row and column directions on the square grid). Our algorithm is deterministic and uses energy minimization technique to find (near) optimal solution in a reasonable time. The experimental evaluation of the new method, using regular hexagon shaped test images, is given. Comparison with reconstructions based on the square grid is also considered.

3

Hierarchies of Stateless Multicounter 5' → 3' Watson-Crick Automata Languages

Egecioglu Ö., Hegedüs L., Nagy B.

Fundamenta Informaticae

|

2011

|

Vol. 110, nr 1-4

111-123

EN

We consider stateless counter machines which mix the features of one-head counter machines and a special type of two-head Watson-Crick automata (WK-automata). Our Watson-Crick counter machines are biologically motivated. They have two heads that read the input starting from the two extremes. The reading process is finished when there are no more symbols between the heads, i.e., every letter of the input is processed by either head. Depending on whether the heads are required to advance at each move, we distinguish between realtime and non-realtime machines. If every counter makes at most k alternations between nondecreasing and decreasing modes in every computation, then the machine is k-reversal. It is reversal bounded if it is k-reversal for some k. In this paper we concentrate on the properties of both deterministic and nondeterministic stateless WK-automata with reversal bounded counters.

4

5'→3' Watson-Crick AutomataWith Several Runs

Leupold P., Nagy B.

Fundamenta Informaticae

|

2010

|

Vol. 104, nr 1/2

71-91

EN

5'→3' WK-automata are Watson-Crick automata whose two heads start on opposite ends of the input word and always run in opposite directions. One full reading in both directions is called a run. We prove that the expressive power of these automata increases with every additional run that they can make, both for deterministic and non-deterministic machines. This defines two incomparable infinite hierarchies of language classes between the regular and the context-sensitive languages. These hierarchies are complemented with classes defined by several restricted variants of 5'→3' WK-automata like stateless automata. Finally we show that several standard problems are undecidable for languages accepted by 5'→3' WK-automata in only one run, for example the emptiness and the finiteness problems.