Unboundedness problems for formal languages (invited talk)

DOI10.4230/LIPICS.FSTTCS.2025.2MaRDI QIDQ7391868zbMATH OpenFDO

Authors Georg Zetzsche

Publication date 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.FSTTCS.2025.2

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Cites work

• A characterization for decidable separability by piecewise testable languages
• A unifying approach for multistack pushdown automata
• An approach to computing downward closures
• Context-bounded analysis for concurrent programs with dynamic creation of threads
• Cost Automata, Safe Schemes, and Downward Closures
• Counter machines with infrequent reversals
• Decidability of a temporal logic problem for Petri nets
• Deciding piecewise testable separability for regular tree languages
• Demystifying Reachability in Vector Addition Systems
• Deterministic and game separability for regular languages of infinite trees
• General Decidability Results for Asynchronous Shared-Memory Programs: Higher-Order and Beyond
• Group separation strikes back
• scientific article; zbMATH DE number 7559472 (Why is no real title available?)
• Invisible pushdown languages
• MULTI-PUSH-DOWN LANGUAGES AND GRAMMARS
• On free monoids partially ordered by embedding
• On multiple context-free grammars
• On the separability problem of VASS reachability languages
• Ordering by Divisibility in Abstract Algebras
• Reachability of scope-bounded multistack pushdown systems
• Regular separability in Büchi VASS
• Regular separability of one counter automata
• Regular separability of Parikh automata
• Regular separability of well-structured transition systems
• Safety of Parametrized Asynchronous Shared-Memory Systems is Almost Always Decidable
• Separability in Büchi VASS and singly nonlinear systems of inequalities
• Separation for dot-depth two
• The complexity of bounded context switching with dynamic thread creation
• The monadic second-order logic of graphs, II: Infinite graphs of bounded width
• The tree width of auxiliary storage
• Tools and Algorithms for the Construction and Analysis of Systems
• Unboundedness and downward closures of higher-order pushdown automata
• Vector addition system reachability problem, a short self-contained proof
• Verifying unboundedness via amalgamation

This page was built for publication: Unboundedness problems for formal languages (invited talk)

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