Finite Automata for the Sub- and Superword Closure of CFLs: Descriptional and Computational Complexity

DOI10.1007/978-3-319-15579-1_37zbMath1451.68142arXiv1410.2737OpenAlexW2150868717MaRDI QIDQ2799199

Georg Bachmeier, Maximilian Schlund, Michael Luttenberger

Publication date: 8 April 2016

Published in: Language and Automata Theory and Applications (Search for Journal in Brave)

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

zbMATH Keywords

subword closuredescriptional complexitylanguage approximationNFA equivalence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (8)

General Decidability Results for Asynchronous Shared-Memory Programs: Higher-Order and Beyond ⋮ Cost Automata, Safe Schemes, and Downward Closures ⋮ On the state complexity of closures and interiors of regular languages with subwords and superwords ⋮ The Ideal Approach to Computing Closed Subsets in Well-Quasi-orderings ⋮ Finite Automata for the Sub- and Superword Closure of CFLs: Descriptional and Computational Complexity ⋮ General decidability results for asynchronous shared-memory programs: higher-order and beyond ⋮ Unnamed Item ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bounded underapproximations
• Effective constructions in well-partially-ordered free monoids
• Analyzing ambiguity of context-free grammars
• Finite Automata for the Sub- and Superword Closure of CFLs: Descriptional and Computational Complexity
• FPsolve: A Generic Solver for Fixpoint Equations over Semirings
• Analyzing Context-Free Grammars Using an Incremental SAT Solver
• On the Reachability Analysis of Acyclic Networks of Pushdown Systems
• The Downward-Closure of Petri Net Languages
• On the State Complexity of Scattered Substrings and Superstrings
• Conservative Ambiguity Detection in Context-Free Grammars
• Ordering by Divisibility in Abstract Algebras
• More on the Size of Higman-Haines Sets: Effective Constructions

This page was built for publication: Finite Automata for the Sub- and Superword Closure of CFLs: Descriptional and Computational Complexity