Stefan Göller

Mathieu Hilaire

Theory Comput. Syst., August, 2024

The AC⁰-Complexity of Visibly Pushdown Languages.

[BibT_eX]

[DOI]

Nathan Grosshans

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

2023

The AC<sup>0</sup>-Complexity Of Visibly Pushdown Languages.

[BibT_eX]

[DOI]

Nathan Grosshans

CoRR, 2023

Weak Bisimulation Finiteness of Pushdown Systems With Deterministic ε-Transitions Is 2-EXPTIME-Complete.

[BibT_eX]

[DOI]

Pawel Parys

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

2021

The Reachability Problem for Two-Dimensional Vector Addition Systems with States.

[BibT_eX]

[DOI]

J. ACM, 2021

2020

Bisimulation Finiteness of Pushdown Systems Is Elementary.

[BibT_eX]

[DOI]

Pawel Parys

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

2019

On Long Words Avoiding Zimin Patterns.

[BibT_eX]

[DOI]

Arnaud Carayol

Theory Comput. Syst., 2019

2018

The Complexity of Bisimulation and Simulation on Finite Systems.

[BibT_eX]

[DOI]

Moses Ganardi

Log. Methods Comput. Sci., 2018

2017

On Büchi One-Counter Automata.

[BibT_eX]

[DOI]

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

2016

Games with bound guess actions.

[BibT_eX]

[DOI]

Thomas Colcombet

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

A Polynomial-Time Algorithm for Reachability in Branching VASS in Dimension One.

[BibT_eX]

[DOI]

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

On the Parallel Complexity of Bisimulation on Finite Systems.

[BibT_eX]

[DOI]

Moses Ganardi

Proceedings of the 25th EACSL Annual Conference on Computer Science Logic, 2016

2015

The Complexity of Decomposing Modal and First-Order Theories.

[BibT_eX]

[DOI]

Jean Christoph Jung

ACM Trans. Comput. Log., 2015

Reachability in Two-Dimensional Vector Addition Systems with States Is PSPACE-Complete.

[BibT_eX]

[DOI]

Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science, 2015

2014

Refining the Process Rewrite Systems Hierarchy via Ground Tree Rewrite Systems.

[BibT_eX]

[DOI]

Anthony Widjaja Lin

ACM Trans. Comput. Log., 2014

Bisimulation equivalence and regularity for real-time one-counter automata.

[BibT_eX]

[DOI]

Petr Jancar

J. Comput. Syst. Sci., 2014

The First-Order Theory of Ground Tree Rewrite Graphs

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2014

2013

Branching-Time Model Checking of One-Counter Processes and Timed Automata.

[BibT_eX]

[DOI]

SIAM J. Comput., 2013

Equivalence of deterministic one-counter automata is NL-complete.

[BibT_eX]

[DOI]

Petr Jancar

Proceedings of the Symposium on Theory of Computing Conference, 2013

Reachability in Register Machines with Polynomial Updates.

[BibT_eX]

[DOI]

Alain Finkel

Christoph Haase

Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

Bisimilarity of Pushdown Automata is Nonelementary.

[BibT_eX]

[DOI]

Proceedings of the 28th Annual ACM/IEEE Symposium on Logic in Computer Science, 2013

The Fixed-Parameter Tractability of Model Checking Concurrent Systems.

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic 2013 (CSL 2013), 2013

2012

Bisimilarity of Pushdown Systems is Nonelementary

[BibT_eX]

[DOI]

CoRR, 2012

Concurrency Makes Simple Theories Hard.

[BibT_eX]

[DOI]

Anthony Widjaja Lin

Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

On Bisimilarity of Higher-Order Pushdown Automata: Undecidability at Order Two.

[BibT_eX]

[DOI]

Christopher H. Broadbent

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2012

Branching-Time Model Checking of Parametric One-Counter Automata.

[BibT_eX]

[DOI]

Proceedings of the Foundations of Software Science and Computational Structures, 2012

A Comparison of Succinctly Represented Finite-State Systems.

[BibT_eX]

[DOI]

Romain Brenguier

Ocan Sankur

Proceedings of the CONCUR 2012 - Concurrency Theory - 23rd International Conference, 2012

The Complexity of Monotone Hybrid Logics over Linear Frames and the Natural Numbers.

[BibT_eX]

[DOI]

Proceedings of the Advances in Modal Logic 9, 2012

2011

Fixpoint Logics over Hierarchical Structures.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2011

Language Equivalence of Deterministic Real-Time One-Counter Automata Is NL-Complete.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

The Complexity of Verifying Ground Tree Rewrite Systems.

[BibT_eX]

[DOI]

Anthony Widjaja Lin

Proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science, 2011

2010

Branching-time Model Checking of One-counter Processes.

[BibT_eX]

[DOI]

Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

Model Checking Succinct and Parametric One-Counter Automata.

[BibT_eX]

[DOI]

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

Bisimilarity of One-Counter Processes Is PSPACE-Complete.

[BibT_eX]

[DOI]

Petr Jancar

Proceedings of the CONCUR 2010 - Concurrency Theory, 21th International Conference, 2010

2009

PDL with intersection and converse: satisfiability and infinite-state model checking.

[BibT_eX]

[DOI]

Carsten Lutz

J. Symb. Log., 2009

On the Computational Complexity of Verifying One-Counter Processes.

[BibT_eX]

[DOI]

Richard Mayr

Anthony Widjaja To

Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, 2009

2008

Computational complexity of propositional dynamic logics.

[BibT_eX]

[DOI]

PhD thesis, 2008

A note on an extension of PDL.

[BibT_eX]

[DOI]

Dirk Nowotka

J. Appl. Log., 2008

Reachability on prefix-recognizable graphs.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2008

2007

On a Non-Context-Free Extension of PDL

[BibT_eX]

[DOI]

Dirk Nowotka

CoRR, 2007

PDL with Intersection and Converse Is 2 EXP-Complete.

[BibT_eX]

[DOI]

Carsten Lutz

Proceedings of the Foundations of Software Science and Computational Structures, 2007

PDL with Intersection and Converse is 2EXP-complete.

[BibT_eX]

[DOI]

Carsten Lutz

Proceedings of the Algorithmic-Logical Theory of Infinite Structures, 28.10. - 02.11.2007, 2007

On the Complexity of Reasoning About Dynamic Policies.

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic, 21st International Workshop, 2007

2006

Infinite State Model-Checking of Propositional Dynamic Logics.

[BibT_eX]

[DOI]

Proceedings of the Computer Science Logic, 20th International Workshop, 2006

2005

Fixpoint Logics on Hierarchical Structures.

[BibT_eX]

[DOI]

Proceedings of the FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science, 2005

2003

Composition on Distributed RUBATO by Affine Transformations and Deformations of Musical Structures.

[BibT_eX]

[DOI]