An approach to computing downward closures

DOI10.1007/978-3-662-47666-6_35MaRDI QIDQ3449495zbMATH OpenOpenAlexFDO

Authors Georg Zetzsche

Publication date 4 November 2015

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

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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).

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

Cites work

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

Cited in

(19)

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

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)