An approach to computing downward closures

DOI10.1007/978-3-662-47666-6_35zbMATH Open1440.68166arXiv1503.01068OpenAlexW1646789098MaRDI QIDQ3449495FDOQ3449495

Authors: Georg Zetzsche 

Publication date: 4 November 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Abstract: The downward closure of a word language is the set of all (not necessarily contiguous) subwords of its members. It is well-known that the downward closure of any language is regular. While the downward closure appears to be a powerful abstraction, algorithms for computing a finite automaton for the downward closure of a given language have been established only for few language classes. This work presents a simple general method for computing downward closures. For language classes that are closed under rational transductions, it is shown that the computation of downward closures can be reduced to checking a certain unboundedness property. This result is used to prove that downward closures are computable for (i) every language class with effectively semilinear Parikh images that are closed under rational transductions, (ii) matrix languages, and (iii) indexed languages (equivalently, languages accepted by higher-order pushdown automata of order 2).

Full work available at URL: https://arxiv.org/abs/1503.01068

Recommendations

• The complexity of downward closure comparisons
• Computing downward closures for stacked counter automata
• On the state complexity of closures and interiors of regular languages with subwords and superwords
• The downward-closure of Petri net languages
• Unboundedness and downward closures of higher-order pushdown automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Undecidable problems in unreliable computations.
• Using forward reachability analysis for verification of lossy channel systems
• Indexed Grammars—An Extension of Context-Free Grammars
• On multiple context-free grammars
• Reachability analysis of pushdown automata: Application to model-checking
• On free monoids partially ordered by embedding
• Effective constructions in well-partially-ordered free monoids
• The size of Higman-Haines sets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A relationship between ETOL and EDTOL languages
• On derivation trees of indexed grammars - an extension of the uvwxy- theorem
• A shrinking lemma for indexed languages
• A pumping lemma for pushdown graphs of any level
• On infinite words determined by indexed languages
• Computing downward closures for stacked counter automata
• The downward-closure of Petri net languages
• Regular cost functions. I: Logic and algebra over words
• An approach to computing downward closures
• Model checking vector addition systems with one zero-test
• A pumping lemma for collapsible pushdown graphs of level 2

Cited In (20)

• Computing maximal Kleene closures that are embeddable in a given subword-closed language
• General Decidability Results for Asynchronous Shared-Memory Programs: Higher-Order and Beyond
• The Complexity of the Diagonal Problem for Recursion Schemes
• A Note on Decidable Separability by Piecewise Testable Languages
• Deciding atomicity of subword-closed languages
• Title not available (Why is that?)
• Unboundedness problems for machines with reversal-bounded counters
• Cost Automata, Safe Schemes, and Downward Closures
• Existential Definability over the Subword Ordering
• An approach to computing downward closures
• General decidability results for asynchronous shared-memory programs: higher-order and beyond
• On finite-index indexed grammars and their restrictions
• Unboundedness problems for languages of vector addition systems
• Title not available (Why is that?)
• The complexity of downward closure comparisons
• Title not available (Why is that?)
• State complexity bounds for projection, shuffle, up- and downward closure and interior on commutative regular languages
• Computing downward closures for stacked counter automata
• Semilinearity of families of languages
• On the state complexity of closures and interiors of regular languages with subwords and superwords

This page was built for publication: An approach to computing downward closures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3449495)