2016/02/10 by Mohamed Faouzi Atig, Dmitry Chistikov, Atig, Mohamed Faouzi +10 · 2 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithm #Alphabet #Artificial intelligence #Automata theory #Automaton #Chemical Synthesis and Analysis #Closure (psychology) #Completeness (order theory) #Computer science #Discrete mathematics #FOS: Computer and information sciences #Finite-state machine #Formal Languages and Automata Theory (cs.FL) #Image (mathematics) #Logic in Computer Science (cs.LO) #Logic, programming, and type systems #Mathematics #Nondeterministic algorithm #Nondeterministic finite automaton #Polynomial #Regular language #Sequence (biology) #Theoretical computer science #Time complexity #cs.FL #cs.LO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1602.03419
arxiv created 2016/02/10 · openalex publication_date 2016/02/10 · arxiv updated 2016/02/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We study the computational and descriptional complexity of the following transformation: Given a one-counter automaton (OCA) A, construct a nondeterministic finite automaton (NFA) B that recognizes an abstraction of the language L(A): its (1) downward closure, (2) upward closure, or (3) Parikh image. For the Parikh image over a fixed alphabet and for the upward and downward closures, we find polynomial-time algorithms that compute such an NFA. For the Parikh image with the alphabet as part of the input, we find a quasi-polynomial time algorithm and prove a completeness result: we construct a sequence of OCA that admits a polynomial-time algorithm iff there is one for all OCA. For all three abstractions, it was previously unknown if appropriate NFA of sub-exponential size exist.