Georg Zetzsche

Proc. ACM Program. Lang., January, 2024

The complexity of separability for semilinear sets and Parikh automata.

[BibT_eX]

[DOI]

Elias Rojas Collins

Chris Köcher

CoRR, 2024

The Power of Hard Attention Transformers on Data Sequences: A Formal Language Theoretic Perspective.

[BibT_eX]

[DOI]

CoRR, 2024

Directed Regular and Context-Free Languages.

[BibT_eX]

[DOI]

Irmak Saglam

Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science, 2024

Slice closures of indexed languages and word equations with counting constraints.

[BibT_eX]

[DOI]

Laura Ciobanu

Shankara Narayanan Krishna

Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, 2024

Verifying Unboundedness via Amalgamation.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, 2024

An Efficient Quantifier Elimination Procedure for Presburger Arithmetic.

[BibT_eX]

[DOI]

Christoph Haase

Khushraj Madnani

Om Swostik Mishra

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

Separability in Büchi VASS and Singly Non-Linear Systems of Inequalities.

[BibT_eX]

[DOI]

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

2023

Context-Bounded Verification of Context-Free Specifications.

[BibT_eX]

[DOI]

Proc. ACM Program. Lang., January, 2023

Existential Definability over the Subword Ordering.

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2023

Knapsack and the power word problem in solvable Baumslag-Solitar groups.

[BibT_eX]

[DOI]

Int. J. Algebra Comput., 2023

Regular Separability in Büchi VASS.

[BibT_eX]

[DOI]

Roland Meyer

Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science, 2023

Checking Refinement of Asynchronous Programs Against Context-Free Specifications.

[BibT_eX]

[DOI]

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Context-Bounded Analysis of Concurrent Programs (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Regular Separators for VASS Coverability Languages.

[BibT_eX]

[DOI]

Chris Köcher

Shankara Narayanan Krishna

Proceedings of the 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2023

Counter Machines with Infrequent Reversals.

[BibT_eX]

[DOI]

Alain Finkel

Khushraj Madnani

Proceedings of the 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2023

Unboundedness Problems for Machines with Reversal-Bounded Counters.

[BibT_eX]

[DOI]

Proceedings of the Foundations of Software Science and Computation Structures, 2023

Priority Downward Closures.

[BibT_eX]

[DOI]

Ashwani Anand

Proceedings of the 34th International Conference on Concurrency Theory, 2023

Monus Semantics in Vector Addition Systems with States.

[BibT_eX]

[DOI]

Proceedings of the 34th International Conference on Concurrency Theory, 2023

2022

Context-bounded verification of thread pools.

[BibT_eX]

[DOI]

Proc. ACM Program. Lang., 2022

General Decidability Results for Asynchronous Shared-Memory Programs: Higher-Order and Beyond.

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2022

Membership Problems in Finite Groups.

[BibT_eX]

[DOI]

Andreas Rosowski

Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science, 2022

The Complexity of Bidirected Reachability in Valence Systems.

[BibT_eX]

[DOI]

Proceedings of the LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2, 2022

Ramsey Quantifiers over Automatic Structures: Complexity and Applications to Verification.

[BibT_eX]

[DOI]

Proceedings of the LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2, 2022

Reachability in Bidirected Pushdown VASS.

[BibT_eX]

[DOI]

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

2021

Context-bounded verification of liveness properties for multithreaded shared-memory programs.

[BibT_eX]

[DOI]

Proc. ACM Program. Lang., 2021

The emptiness problem for valence automata over graph monoids.

[BibT_eX]

[DOI]

Inf. Comput., 2021

A Characterization of Wreath Products Where Knapsack Is Decidable.

[BibT_eX]

[DOI]

Pascal Bergsträßer

Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021

Recent Advances on Reachability Problems for Valence Systems (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the Reachability Problems - 15th International Conference, 2021

Scope-Bounded Reachability in Valence Systems.

[BibT_eX]

[DOI]

Aneesh K. Shetty

S. Krishna

Proceedings of the 32nd International Conference on Concurrency Theory, 2021

2020

Knapsack and the Power Word Problem in Solvable Baumslag-Solitar Groups.

[BibT_eX]

[DOI]

Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

An Approach to Regular Separability in Vector Addition Systems.

[BibT_eX]

[DOI]

Wojciech Czerwinski

Proceedings of the LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, 2020

Extensions of ω-Regular Languages.

[BibT_eX]

[DOI]

Proceedings of the LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, 2020

The Complexity of Knapsack Problems in Wreath Products.

[BibT_eX]

[DOI]

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

Rational Subsets of Baumslag-Solitar Groups.

[BibT_eX]

[DOI]

Michaël Cadilhac

Dmitry Chistikov

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

The Complexity of Bounded Context Switching with Dynamic Thread Creation.

[BibT_eX]

[DOI]

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

2019

Coverability Is Undecidable in One-Dimensional Pushdown Vector Addition Systems with Resets.

[BibT_eX]

[DOI]

Sylvain Schmitz

Proceedings of the Reachability Problems - 13th International Conference, 2019

Presburger arithmetic with stars, rational subsets of graph groups, and nested zero tests.

[BibT_eX]

[DOI]

Christoph Haase

Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science, 2019

Regular Separability and Intersection Emptiness Are Independent Problems.

[BibT_eX]

[DOI]

Proceedings of the 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2019

Languages Ordered by the Subword Order.

[BibT_eX]

[DOI]

Dietrich Kuske

Proceedings of the Foundations of Software Science and Computation Structures, 2019

2018

Knapsack in Graph Groups.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2018

PTL-separability and closures for WQOs on words.

[BibT_eX]

[DOI]

CoRR, 2018

Knapsack Problems for Wreath Products.

[BibT_eX]

[DOI]

Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018

Separability by piecewise testable languages and downward closures beyond subwords.

[BibT_eX]

[DOI]

Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, 2018

Unboundedness Problems for Languages of Vector Addition Systems.

[BibT_eX]

[DOI]

Wojciech Czerwinski

Piotr Hofman

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Bounded Context Switching for Valence Systems.

[BibT_eX]

[DOI]

Roland Meyer

Sebastian Muskalla

Proceedings of the 29th International Conference on Concurrency Theory, 2018

2017

On Boolean Closed Full Trios and Rational Kripke Frames.

[BibT_eX]

[DOI]

Dietrich Kuske

Theory Comput. Syst., 2017

A Characterization for Decidable Separability by Piecewise Testable Languages.

[BibT_eX]

[DOI]

Discret. Math. Theor. Comput. Sci., 2017

The Complexity of Knapsack in Graph Groups.

[BibT_eX]

[DOI]

Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

Decidability, complexity, and expressiveness of first-order logic over the subword ordering.

[BibT_eX]

[DOI]

Simon Halfon

Philippe Schnoebelen

Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, 2017

2016

Monoids as Storage Mechanisms.

[BibT_eX]

[DOI]

PhD thesis, 2016

Monoids as Storage Mechanisms.

[BibT_eX]

[DOI]

Bull. EATCS, 2016

Permutations of context-free, ET0L and indexed languages.

[BibT_eX]

[DOI]

Discret. Math. Theor. Comput. Sci., 2016

Knapsack in Graph Groups, HNN-Extensions and Amalgamated Products.

[BibT_eX]

[DOI]

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

First-order logic with reachability for infinite-state systems.

[BibT_eX]

[DOI]

Emanuele D'Osualdo

Roland Meyer

Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, 2016

The complexity of regular abstractions of one-counter languages.

[BibT_eX]

[DOI]

Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, 2016

The Complexity of Downward Closure Comparisons.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups.

[BibT_eX]

[DOI]

Daniel König

Proceedings of the Algebra and Computer Science, 2016

2015

Rational subsets and submonoids of wreath products.

[BibT_eX]

[DOI]

Benjamin Steinberg

Inf. Comput., 2015

Computing Downward Closures for Stacked Counter Automata.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

The Emptiness Problem for Valence Automata or: Another Decidable Extension of Petri Nets.

[BibT_eX]

[DOI]

Proceedings of the Reachability Problems - 9th International Workshop, 2015

An Approach to Computing Downward Closures.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014

On Boolean closed full trios and rational Kripke frames.

[BibT_eX]

[DOI]

Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

The Monoid of Queue Actions.

[BibT_eX]

[DOI]

Martin Huschenbett

Dietrich Kuske

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

2013

Semilinearity and Context-Freeness of Languages Accepted by Valence Automata.

[BibT_eX]

[DOI]

P. Buckheister

Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

Silent Transitions in Automata with Storage.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2011

Toward Understanding the Generative Capacity of Erasing Rules in Matrix Grammars.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2011

On the Capabilities of Grammars, Automata, and Transducers Controlled by Monoids.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

A Sufficient Condition for Erasing Productions to Be Avoidable.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory - 15th International Conference, 2011

2010

On Erasing Productions in Random Context Grammars.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

2009

Properties of Multiset Language Classes Defined by Multiset Pushdown Automata.

[BibT_eX]

[DOI]

Manfred Kudlek

Patrick Totzke

Fundam. Informaticae, 2009

Multiset Pushdown Automata.

[BibT_eX]

[DOI]

Manfred Kudlek

Patrick Totzke

Fundam. Informaticae, 2009

Erasing in Petri Net Languages and Matrix Grammars.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 13th International Conference, 2009

2008

Language Classes Defined by Concurrent Finite Automata.

[BibT_eX]

[DOI]

Matthias Jantzen

Manfred Kudlek

Fundam. Informaticae, 2008

Petri Net Controlled Finite Automata.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2008

Labeled Step Sequences in Petri Nets.

[BibT_eX]

[DOI]

Matthias Jantzen