Decidable inequalities over infinite trees

DOI10.29007/S21NzbMATH Open1415.68059OpenAlexW2908255398MaRDI QIDQ5222948FDOQ5222948

Authors: Sabine Bauer, Steffen Jost, Martin Hofmann 

Publication date: 4 July 2019

Published in: EPiC Series in Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.29007/s21n

Recommendations

• Linear constraints over infinite trees
• Decidable linear list constraints
• Finite and Rational Tree Constraints
• Equational and membership constraints for infinite trees
• Expressiveness of full first-order constraints in the algebra of finite or infinite trees

zbMATH Keywords

constraint satisfactionlinear inequalitiespushdown automataresource analysisregular languagesinfinite treesword combinatorics

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Combinatorics on words (68R15) Decidability of theories and sets of sentences (03B25)

Cited In (10)

• ATLAS: automated amortised complexity analysis of self-adjusting data structures
• Title not available (Why is that?)
• Two decades of automatic amortized resource analysis
• Choice functions and well-orderings over the infinite binary tree
• Title not available (Why is that?)
• Equational and membership constraints for infinite trees
• Title not available (Why is that?)
• The Computable Dimension of I-Trees of Infinite Height
• Linear constraints over infinite trees
• Type-based analysis of logarithmic amortised complexity

This page was built for publication: Decidable inequalities over infinite trees

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