Fundamenta Informaticae - Volume 123, issue 1

Authors: Ciabattoni, Agata | Freivalds, Rusin | Kučera, Antonín | Potapov, Igor | Szeider, Stefan

Article Type: Other

DOI: 10.3233/FI-2013-796

Citation: Fundamenta Informaticae, vol. 123, no. 1, pp. v-vi, 2013

Authors: Bell, Paul C. | Halava, Vesa | Hirvensalo, Mika

Article Type: Research Article

Abstract: We show that several problems concerning probabilistic finite automata of a fixed dimension and a fixed number of letters for bounded cut-point and strict cut-point languages are algorithmically undecidable by a reduction of Hilbert's tenth problem. We then consider the set of so called “F-Problems” (emptiness, infiniteness, containment, disjointness, universe and equivalence) and show that they are also undecidable for bounded (non-)strict cut-point languages on probabilistic finite automata. For a finite set of matrices $\{M_1, M_2, \ldots ,M_k\} \subseteq \mathbb{Q}^{t \times t}$, we then consider the decidability of computing the maximal spectral radius of any matrix in the set $X …= \{M^{j_1}_1 M^{j_2}_2 \cdot M^{j_k}_k \vert j_1, j_2,\ldots, j_k \geq 0\}$, which we call a bounded matrix language. Using an encoding of a probabilistic finite automaton shown in the paper, we prove the surprising result that determining if the maximal spectral radius of a bounded matrix language is less than or equal to one is undecidable, but determining whether it is strictly less than one is in fact decidable (which is similar to a result recently shown for quantum automata). Show more

Keywords: Probabilistic finite automata, Bounded languages, Formal power series, Undecidability, Hilbert's tenth problem

DOI: 10.3233/FI-2013-797

Citation: Fundamenta Informaticae, vol. 123, no. 1, pp. 1-14, 2013

Authors: Chaloupka, Jakub

Article Type: Research Article

Abstract: We consider a two-player infinite game with zero-reachability objectives played on a 2-dimensional vector addition system with states (VASS), the states of which are divided between the two players. Brázdil, Jančar, and Kučera (2010) have shown that for k > 0, deciding the winner in a game on k-dimensional VASS is in (k − 1)-EXPTIME. In this paper, we show that, for k = 2, the problem is in P, and thus improve the EXPTIME upper bound.

DOI: 10.3233/FI-2013-798

Citation: Fundamenta Informaticae, vol. 123, no. 1, pp. 15-42, 2013

Authors: Fasching, Oliver

Article Type: Research Article

Abstract: We extend propositional Gödel logic by a unary modal operator, which we interpret as Gödel homomorphisms, i.e. functions [0, 1] → [0, 1] that distribute over the interpretations of the binary connectives of Gödel logic. We show weak completeness of the propositional fragment w.r.t. a simple superintuitionistic Hilbert-type proof system, and we prove that validity does not change if we use the function class of continuous, strictly increasing functions. We also give proof systems for restrictions to sub- and superdiagonal functions.

Keywords: Gödel logic, superintuitionistic logic, modal logic, truth stressers

DOI: 10.3233/FI-2013-799

Citation: Fundamenta Informaticae, vol. 123, no. 1, pp. 43-57, 2013

Authors: Ganian, Robert | Hliněný, Petr | Obdržálek, Jan

Article Type: Research Article

Abstract: We provide a parameterized algorithm for the propositional model counting problem #SAT, the runtime of which has a single-exponential dependency on the rank-width of the signed graph of a formula. That is, our algorithm runs in time $\cal{O}(t^3 \cdot 2^{3t(t+1)/2} \cdot \vert\phi\vert)$ for a width-t rank-decomposition of the input φ, and can be of practical interest for small values of rank-width. Previously, analogical algorithms have been known – e.g. [Fischer, Makowsky, and Ravve] – with a single-exponential dependency on the clique-width k of the signed graph of a formula with a given k-expression. Our algorithm presents an exponential runtime improvement …over the worst-case scenario of the previous one, since clique-width reaches up to exponentially higher values than rankwidth. We also provide an algorithm for the MAX-SAT problem along the same lines. Show more

Keywords: propositional model counting, satisfiability, rank-width, clique-width, parameterized Complexity

DOI: 10.3233/FI-2013-800

Citation: Fundamenta Informaticae, vol. 123, no. 1, pp. 59-76, 2013

Authors: Muiño, David Picado

Article Type: Research Article

Abstract: We present a family of consequence relations for graded inference among Łukasiewicz sentences. Given a set of premises and a threshold η, we consider consequences those sentences entailed to hold to at least some degree ζ whenever the premises hold to a degree at least η. We focus on the study of some aspects and features of the consequence relations presented and, in particular, on the effect of variations in the thresholds η, ζ.

DOI: 10.3233/FI-2013-801

Citation: Fundamenta Informaticae, vol. 123, no. 1, pp. 77-95, 2013

Authors: Sawa, Zdeněk

Article Type: Research Article

Abstract: In languages over a unary alphabet, i.e., an alphabet with only one letter, words can be identified with their lengths. It is well known that each regular language over a unary alphabet can be represented as the union of a finite number of arithmetic progressions. Given a nondeterministic finite automaton (NFA) working over a unary alphabet (a unary NFA), the arithmetic progressions representing the language accepted by the automaton can be easily computed by the determinization of the given NFA. However, the number of the arithmetic progressions computed in this way can be exponential with respect to the size of …the original automaton. Chrobak (1986) has shown that in fact O(n2 ) arithmetic progressions are sufficient for the representation of the language accepted by a unary NFA with n states, and Martinez (2002) has shown how these progressions can be computed in polynomial time. Recently, To (2009) has pointed out that Chrobak's construction and Martinez's algorithm, which is based on it, contain a subtle error and has shown how to correct this error. Geffert (2007) presented an alternative proof of Chrobak's result, also improving some of the bounds. In this paper, a new simpler and more efficient algorithm for the same problem is presented, using some ideas from Geffert (2007). The time complexity of the presented algorithm is O(n2 (n + m)) and its space complexity is O(n + m), where n is the number of states and m the number of transitions of a given unary NFA. Show more

DOI: 10.3233/FI-2013-802

Citation: Fundamenta Informaticae, vol. 123, no. 1, pp. 97-106, 2013

Authors: Yakaryılmaz, Abuzer | Say, A. C. Cem

Article Type: Research Article

Abstract: It is a widely believed, though unproven, conjecture that the capability of postselection increases the language recognition power of both probabilistic and quantum polynomial-time computers. It is also unknown whether polynomial-time quantum machines with postselection are more powerful than their probabilistic counterparts with the same resource restrictions. We approach these problems by imposing additional constraints on the resources to be used by the computer, and are able to prove for the first time that postselection does augment the computational power of both classical and quantum computers, and that quantum does outperform probabilistic in this context, under simultaneous time and space …bounds in a certain range. We also look at postselected versions of space-bounded classes, as well as those corresponding to error-free and one-sided error recognition, and provide classical characterizations. It is shown that NL would equal RL if the randomized machines had the postselection capability. Show more

Keywords: postselection, quantum Turing machines, probabilistic Turing machines, space-bounded computation, one-sided error, zero error

DOI: 10.3233/FI-2013-803

Citation: Fundamenta Informaticae, vol. 123, no. 1, pp. 107-134, 2013