Search

In this work, we exploit the power of finite ambiguity for the complementation problem of Büchi automata by using reduced run directed acyclic graphs (DAGs) over infinite words, in which each vertex has at most one predecessor; these reduced run DAGs have only a finite number of infinite runs, thus obtaining the finite ambiguity in Büchi complementation. We show how to use this type of reduced run DAGs as a unified tool to optimize both rank-based and slice-based complementation constructions for Büchi automata with a finite degree of ambiguity. As a result, given a Büchi automaton with n states and a finite degree of ambiguity, the number of states in the complementary Büchi automaton constructed by the classical rank-based and slice-based complementation constructions can be improved from 2 O (n log ⁡ n) and O ((3 n) n) to O (6 n) ⊆ 2 O (n) and O (4 n) , respectively. We further show how to construct such reduced run DAGs for limit deterministic Büchi automata and obtain a specialized complementation algorithm, thus demonstrating the generality of the power of finite ambiguity. [ABSTRACT FROM AUTHOR]

The paper demonstrates the non-closure of the family of unambiguous linear languages (that is, those defined by unambiguous linear context-free grammars) under complementation. To be precise, a particular unambiguous linear grammar is presented, and it is proved that the complement of this language is not defined by any context-free grammar. This also constitutes an alternative proof for the result of Hibbard and Ullian ("The independence of inherent ambiguity from complementedness among context-free languages", JACM , 1966) on the non-closure of the unambiguous languages under complementation. [ABSTRACT FROM AUTHOR]

A morphism g is ambiguous with respect to a word u if there exists a second morphism h ≠ g such that g (u) = h (u). Otherwise g is unambiguous with respect to u. Thus unambiguous morphisms are those for which the structure of the morphism is preserved in the image. Ambiguity has so far been studied for morphisms of free monoids, where several characterisations exist for the set of words u permitting an (injective) unambiguous morphism. In the present paper, we consider ambiguity of morphisms of free groups, and consider possible analogies to the existing characterisations in the free monoid. While a direct generalisation results in a trivial situation where all morphisms are ambiguous, we discuss some natural and well-motivated reformulations, and provide a characterisation of words in a free group that permit a morphism which is "as unambiguous as possible". [ABSTRACT FROM AUTHOR]

Probabilistic automata are an extension of nondeterministic finite automata in which transitions are annotated with probabilities. Despite its simplicity, this model is very expressive and many algorithmic questions are undecidable. In this work we focus on the emptiness problem (and its variant the value problem), which asks whether a given probabilistic automaton accepts some word with probability greater than a given threshold. We consider finitely ambiguous probabilistic automata. Our main contributions are to construct efficient algorithms for analysing finitely ambiguous probabilistic automata through a reduction to a multi-objective optimisation problem called the stochastic path problem. We obtain a polynomial time algorithm for approximating the value of probabilistic automata of fixed ambiguity and a quasi-polynomial time algorithm for the emptiness problem for 2-ambiguous probabilistic automata. We complement these positive results by an inapproximability result stating that the value of finitely ambiguous probabilistic automata cannot be approximated unless P = NP. [ABSTRACT FROM AUTHOR]

An automaton is unambiguous if for every input it has at most one accepting computation. An automaton is finitely (respectively, countably) ambiguous if for every input it has at most finitely (respectively, countably) many accepting computations. An automaton is boundedly ambiguous if there is k ∈ N , such that for every input it has at most k accepting computations. We consider nondeterministic Büchi automata (NBA) over infinite trees and prove that it is decidable in polynomial time, whether an automaton is unambiguous, boundedly ambiguous, finitely ambiguous, or countably ambiguous. [ABSTRACT FROM AUTHOR]