Manfred Droste ; Werner Kuich - Weighted omega-Restricted One Counter Automata

lmcs:3105 - Logical Methods in Computer Science, March 6, 2018, Volume 14, Issue 1 - https://doi.org/10.23638/LMCS-14(1:21)2018
Weighted omega-Restricted One Counter AutomataArticle

Authors: Manfred Droste ; Werner Kuich

    Let $S$ be a complete star-omega semiring and $\Sigma$ be an alphabet. For a weighted $\omega$-restricted one-counter automaton $\mathcal{C}$ with set of states $\{1, \dots, n\}$, $n \geq 1$, we show that there exists a mixed algebraic system over a complete semiring-semimodule pair ${((S \ll \Sigma^* \gg)^{n\times n}, (S \ll \Sigma^{\omega}\gg)^n)}$ such that the behavior $\Vert\mathcal{C} \Vert$ of $\mathcal{C}$ is a component of a solution of this system. In case the basic semiring is $\mathbb{B}$ or $\mathbb{N}^{\infty}$ we show that there exists a mixed context-free grammar that generates $\Vert\mathcal{C} \Vert$. The construction of the mixed context-free grammar from $\mathcal{C}$ is a generalization of the well-known triple construction in case of restricted one-counter automata and is called now triple-pair construction for $\omega$-restricted one-counter automata.


    Volume: Volume 14, Issue 1
    Published on: March 6, 2018
    Accepted on: February 15, 2018
    Submitted on: January 31, 2017
    Keywords: Computer Science - Formal Languages and Automata Theory,68Q45, 68Q70 (Primary) 68Q42 (Secondary),F.1.1,F.4.3
    Funding:
      Source : OpenAIRE Graph
    • Algebraic Structures and Fixed Point Operations in Computer Science; Funder: Austrian Science Fund (FWF); Code: I 1661

    Consultation statistics

    This page has been seen 1196 times.
    This article's PDF has been downloaded 266 times.