Fundamenta Informaticae - Volume 152, issue 4

Authors: Kopczyński, Eryk

Article Type: Research Article

Abstract: This paper is an introduction to the computational complexity theory. I believe that the standard courses in complexity theory make some things much more important than they really are, while things which I find extremely interesting are marginalized. Thus, it can be seen as my subjective view on what is important and interesting in computational complexity, and what is not. We state the basic facts from computational complexity theory using the blackboard computations (one-dimensional cellular automata) as the standard computation model; we argue the benefits of such approach. This article is somewhat based on my series of talks from …Warsztaty Logiczne 2014 in Białka Tatrzańska, although these talks covered more topics, such as NL=coNL , and links between BPP and the polynomial hierarchy. Show more

Keywords: cellular automata, alternation, Savitch theorem

DOI: 10.3233/FI-2017-1523

Citation: Fundamenta Informaticae, vol. 152, no. 4, pp. 323-339, 2017

Authors: Loukanova, Roussanka

Article Type: Research Article

Abstract: This paper is a review of the formal definitions of a description language of functional models of Constraint-Based Lexicalized Grammar (CBLG), with a notion of well-formedness, models of linguistic objects, and the corresponding denotation function. The language uses feature-value descriptions. A formalization of CBLG is presented via definitions of several classes of objects by this formal language using mutual recursion. The core engine of the CBLG formal grammar is a hierarchical type system associated with constraints for representation of linguistic information. The constraints are classified as linguistic principles, grammar rules, lexical entries, lexical rules, and semantic representations. The formal system …of CBLG targets a computational approach to human language grammar. Show more

Keywords: grammar models, functional formalization, types, natural language, feature-values

DOI: 10.3233/FI-2017-1524

Citation: Fundamenta Informaticae, vol. 152, no. 4, pp. 341-372, 2017

Authors: Peng, Xindong | Dai, Jingguo | Yuan, Huiyong

Article Type: Research Article

Abstract: Interval-valued fuzzy soft decision making problems have obtained great popularity recently. Most of the current methods depend on level soft set that provide choice value of alternatives to be ranked. Such choice value always encounter the equal condition that the optimal alternative can’t be gained. Most important of all, the current decision making procedure is not in accordance with the way that the decision makers think about the decision making problems. In this paper, we initiate a new axiomatic definition of interval-valued fuzzy distance measure and similarity measure, which is expressed by interval-valued fuzzy number (IVFN) that will reduce the …information loss and keep more original information. Later, the objective weights of various parameters are determined via grey system theory, meanwhile, we develop the combined weights, which can show both the subjective information and the objective information. Then, we present three algorithms to solve interval-valued fuzzy soft decision making problems by Multi-Attributive Border Approximation area Comparison (MABAC), Evaluation based on Distance from Average Solution (EDAS) and new similarity measure. Three approaches solve some unreasonable conditions and promote the development of decision making methods. Finally, the effectiveness and feasibility of approaches are demonstrated by some numerical examples. Show more

Keywords: Interval fuzzy soft sets, combined weights, MABAC, EDAS, similarity measure

DOI: 10.3233/FI-2017-1525

Citation: Fundamenta Informaticae, vol. 152, no. 4, pp. 373-396, 2017

Authors: Šíma, Jiří | Žák, Stanislav

Article Type: Research Article

Abstract: We formulate a very general tight diagonalization method for the Blum complexity measures satisfying two additional axioms related to our diagonalizer machine. We apply this method to two new, mutually related, distance and buffer complexities of Turing machine computations which are important nontrivial examples of natural Blum complexity measures different from time and space. In particular, these measures capture how many times the worktape head needs to move a certain distance during the computation which corresponds to the number of necessary block uploads into a buffer cache memory. We start this study by proving a tight separation which shows that …a very small increase in the distance or buffer complexity bound (roughly from f (n ) to f (n + 1)) brings provably more computational power to both deterministic and nondeterministic Turing machines even for unary languages. We also obtain hierarchies of the distance and buffer complexity classes. Show more

DOI: 10.3233/FI-2017-1526

Citation: Fundamenta Informaticae, vol. 152, no. 4, pp. 397-409, 2017

Authors: Woźna-Szcześniak, Bożena | Zbrzezny, Agnieszka M. | Zbrzezny, Andrzej

Article Type: Research Article

Abstract: We investigate a quasi-optimal cost reachability problem for weighted timed automata. We use a translation to the satisfiability modulo theories (SMT) problem to solve the problem. In particular, we show how to find a run of length k ∈ IN that starts at the initial state and terminates at a state containing the target location, its total cost belongs to the interval [c ; c + 1), for some natural number c ∈ IN, and the cost of each other run of length k , which also leads from the initial state to a state containing the …target location, is greater or equal to c . This kind of run is called k -quasi -optimal . We exemplify the use of our solution to the investigated problem by means of the weighted timed generic pipeline protocol and the weighted job shop scheduling problem , and we provide some preliminary experimental results. Show more

DOI: 10.3233/FI-2017-1527

Citation: Fundamenta Informaticae, vol. 152, no. 4, pp. 411-433, 2017

Article Type: Other

Citation: Fundamenta Informaticae, vol. 152, no. 4, pp. 435-436, 2017