Cost Automata, Safe Schemes, and Downward Closures

DOI10.3233/fi-222145arXiv2004.12187OpenAlexW3037216630MaRDI QIDQ6044492

Thomas Colcombet, Lorenzo Clemente, David Barozzini, Paweł Parys

Publication date: 19 May 2023

Published in: Fundamenta Informaticae (Search for Journal in Brave)

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

zbMATH Keywords

higher-order recursion schemescost automatadownward closurescost logicssafe recursion schemes

Mathematics Subject Classification ID

Computer science (68-XX)

Related Items (1)

Unboundedness problems for machines with reversal-bounded counters

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Krivine machines and higher-order schemes
• Effective constructions in well-partially-ordered free monoids
• Infinite \(\lambda\)-calculus and types
• Infinitary lambda calculus
• Automata, logics, and infinite games. A guide to current research
• The IO and OI hierarchies revisited
• Finite Automata for the Sub- and Superword Closure of CFLs: Descriptional and Computational Complexity
• Unboundedness and downward closures of higher-order pushdown automata
• Regular Cost Functions, Part I: Logic and Algebra over Words
• A Note on Decidable Separability by Piecewise Testable Languages
• Computing Downward Closures for Stacked Counter Automata
• Saturation-Based Model Checking of Higher-Order Recursion Schemes.
• Simply typed fixpoint calculus and collapsible pushdown automata
• Collapsible Pushdown Automata and Labeled Recursion Schemes: Equivalence, Safety and Effective Selection
• A Practical Linear Time Algorithm for Trivial Automata Model Checking of Higher-Order Recursion Schemes
• Weak Cost Monadic Logic over Infinite Trees
• On the Expressive Power of Cost Logics over Infinite Words
• A Type System Describing Unboundedness
• An Approach to Computing Downward Closures
• The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata
• The Downward-Closure of Petri Net Languages
• On Global Model Checking Trees Generated by Higher-Order Recursion Schemes
• The Theory of Stabilisation Monoids and Regular Cost Functions
• Deciding Piecewise Testable Separability for Regular Tree Languages
• The Complexity of Downward Closure Comparisons
• Two-way cost automata and cost logics over infinite trees
• The Diagonal Problem for Higher-Order Recursion Schemes is Decidable
• Games with bound guess actions
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• Computer Science Logic
• A model for behavioural properties of higher-order programs
• Collapsible Pushdown Automata and Recursion Schemes
• Model Checking Higher-Order Programs
• A type-directed abstraction refinement approach to higher-order model checking
• Indexed Grammars—An Extension of Context-Free Grammars
• MULTI-PUSH-DOWN LANGUAGES AND GRAMMARS
• Ordering by Divisibility in Abstract Algebras
• The Safe Lambda Calculus

This page was built for publication: Cost Automata, Safe Schemes, and Downward Closures