Word Equations with Length Constraints: What's Decidable?

No abstract is available for this paper.

• Publication year

  2012

• Venue

  Haifa Verification Conference

• Publication date

  2012-11-06

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/978-3-642-39611-3_21
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• HAMPI: A String Solver for Testing, Analysis and Vulnerability Detection

  2011cited by this paper
• Assessing the relationship between ad volume and awareness of a tobacco education media campaign

  2010cited by this paper
• A Symbolic Execution Framework for JavaScript

  2010influential reference
• HAMPI: a solver for string constraints

  2009cited by this paper
• Sound and precise analysis of web applications for injection vulnerabilities

  2007cited by this paper
• Dynamic test input generation for database applications

  2007cited by this paper
• EXE: automatically generating inputs of death

  2006cited by this paper
• An efficient algorithm for solving word equations

  2006influential reference
• Hilbert’s Tenth Problem: Diophantine Equations in the Twentieth Century

  2006cited by this paper
• New Computational Paradigms

  2005cited by this paper
• DART: directed automated random testing

  2005cited by this paper
• On Word Equations in One Variable

  2002cited by this paper
• Automatic structures

  2000cited by this paper
• Two-variable word equations

  2000cited by this paper
• Quadratic Word Equations

  1999cited by this paper
• Satisfiability of word equations with constants is in PSPACE

  1999influential reference
• Satisfiability of word equations with constants is in NEXPTIME

  1999cited by this paper
• The expressibility of languages and relations by word equations

  1997influential reference
• Undecidability of the positive ∀∃3-theory of a free semigroup

  1995cited by this paper
• Hilbert's tenth problem

  1993cited by this paper
• Word Equations with Two Variables

  1991cited by this paper
• Makanin's Algorithm for Word Equations - Two Improvements and a Generalization

  1990cited by this paper
• Word Equations and Related Topics

  1990cited by this paper
• Introduction to Automata Theory, Languages and Computation

  1979influential reference
• The Problem of Solvability of Equations in a Free Semigroup

  1977cited by this paper
• Mathematical logic

  1967cited by this paper
• Concatenation as a basis for arithmetic

  1946cited by this paper

• On Solving String Equations via Powers and Parikh Images

  2026cites this paper
• Word equations in synergy with regular constraints (extended version)

  2025cites this paper
• A Separation Logic for Sequences in Block-Based Cloud Storage Systems and Its Decidability

  2025cites this paper
• Decision Procedure for A Theory of String Sequences

  2025cites this paper
• Satisfiability of Context-free String Constraints with Subword-ordering and Transducers

  2024cites this paper
• A Solver for Arrays with Concatenation

  2023cites this paper
• Solving String Constraints with Lengths by Stabilization

  2023influential citation
• Reasoning About Vectors: Satisfiability Modulo a Theory of Sequences

  2023cites this paper
• Decision Procedures for Sequence Theories (Technical Report)

  2023influential citation
• Chain-Free String Constraints (Technical Report)

  2023cites this paper
• A Symbolic Algorithm for the Case-Split Rule in Solving Word Constraints with Extensions (Technical Report)

  2023cites this paper
• Witnessability of Undecidable Problems

  2023influential citation
• On the Expressive Power of String Constraints

  2023influential citation
• Group equations with abelian predicates

  2022cites this paper
• Formal Languages via Theories over Strings

  2022cites this paper
• Reasoning About Vectors using an SMT Theory of Sequences

  2022cites this paper
• On the Satisfiability of Context-free String Constraints with Subword-Ordering

  2022cites this paper
• Word Equations in Synergy with Regular Constraints (Technical Report)

  2022cites this paper
• Z3str4: A Multi-armed String Solver

  2021cites this paper
• On equations and first-order theory of one-relator monoids

  2021cites this paper
• On Solving String Constraints

  2021cites this paper
• Solving String Constraints With Regex-Dependent Functions Through Transducers With Priorities And Variables (Technical Report)

  2021cites this paper
• BIROn - Birkbeck Institutional Research Online is decidable about string constraints with the ReplaceAll function.

  2021cites this paper
• Solving string constraints with Regex-dependent functions through transducers with priorities and variables

  2021cites this paper
• First-order concatenation theory with bounded quantifiers

  2020cites this paper
• String Constraints with Concatenation and Transducers Solved Efficiently (Technical Report)

  2020cites this paper
• First-order concatenation theory with bounded quantifiers

  2020cites this paper
• An SMT Solver for Regular Expressions and Linear Arithmetic over String Length

  2020cites this paper
• A Symbolic Algorithm for the Case-Split Rule in String Constraint Solving

  2020cites this paper
• Programming Languages and Systems: 18th Asian Symposium, APLAS 2020, Fukuoka, Japan, November 30 – December 2, 2020, Proceedings

  2020cites this paper
• Inter-theory dependency analysis for SMT string solvers

  2020cites this paper
• A Length-aware Regular Expression SMT Solver

  2020cites this paper
• A Decision Procedure for Path Feasibility of String Manipulating Programs with Integer Data Type

  2020cites this paper
• Efficient handling of string-number conversion

  2020cites this paper
• On the Separability Problem of String Constraints

  2020cites this paper
• Monadic Decomposition in Integer Linear Arithmetic

  2020cites this paper
• A Survey on String Constraint Solving

  2020cites this paper
• Automated Deduction – CADE 27: 27th International Conference on Automated Deduction, Natal, Brazil, August 27–30, 2019, Proceedings

  2019cites this paper
• Monadic Decomposability of Regular Relations

  2019cites this paper
• Syntax-Guided Rewrite Rule Enumeration for SMT Solvers

  2019cites this paper
• The teaching complexity of erasing pattern languages with bounded variable frequency

  2019cites this paper
• Unification modulo Lists with Reverse as Solving Simple Sets of Word Equations

  2019cites this paper
• Theory and practice of string solvers (invited talk abstract)

  2019cites this paper
• Equations and first-order theory of one-relator and word-hyperbolic monoids.

  2019cites this paper
• Unification Modulo Lists with Reverse Relation with Certain Word Equations

  2019cites this paper
• Chain-Free String Constraints

  2019cites this paper
• Notes on Fragments of First-Order Concatenation Theory

  2018cites this paper
• Parameterized model counting for string and numeric constraints

  2018cites this paper
• A Decision Procedure for String Logic with Quadratic Equations, Regular Expressions and Length Constraints

  2018influential citation
• The Satisfiability of Extended Word Equations: The Boundary Between Decidability and Undecidability

  2018cites this paper
• Decidable and Undecidable Fragments of First-Order Concatenation Theory

  2018cites this paper
• Sailing Routes in the World of Computation

  2018cites this paper
• Rewrites for SMT Solvers using Syntax-Guided Enumeration ( Work in Progress )

  2018cites this paper
• Decidable Logics Combining Word Equations, Regular Expressions and Length Constraints

  2018influential citation
• Decision procedures for path feasibility of string-manipulating programs with complex operations

  2018cites this paper
• Quadratic Word Equations with Length Constraints, Counter Systems, and Presburger Arithmetic with Divisibility

  2018cites this paper
• The Satisfiability of Word Equations: Decidable and Undecidable Theories

  2018cites this paper
• Designing Theory Solvers with Extensions

  2017cites this paper
• Constraint normalization and parameterized caching for quantitative program analysis

  2017cites this paper
• String constraints with concatenation and transducers solved efficiently

  2017cites this paper
• Constraint Normalization and Parameterized Caching for antitative Program Analysis

  2017cites this paper
• Decidability, complexity, and expressiveness of first-order logic over the subword ordering

  2017cites this paper
• What Is Decidable about String Constraints with the ReplaceAll Function

  2017cites this paper
• A Novel Approach to String Constraint Solving

  2017cites this paper
• Flatten and conquer: a framework for efficient analysis of string constraints

  2017cites this paper
• What is decidable about string constraints with the ReplaceAll function

  2017cites this paper
• A Brief Survey of Related Work

  2017cites this paper
• Scaling Up DPLL(T) String Solvers Using Context-Dependent Simplification

  2017cites this paper
• String analysis for side channels with segmented oracles

  2016cites this paper
• A Solver for a Theory of Strings and Bit-vectors

  2016cites this paper
• Undecidability of a Theory of Strings, Linear Arithmetic over Length, and String-Number Conversion

  2016cites this paper
• MiniZinc with Strings

  2016cites this paper
• Z3str2: an efficient solver for strings, regular expressions, and length constraints

  2016influential citation
• Foundations for Decision Problems in String Logic with Equations, Regular Membership and Length Constraints (Technical Report)

  2016cites this paper
• String Solving with Word Equations and Transducers: Towards a Logic for Analysing Mutation XSS (Full Version)

  2016cites this paper
• An efficient SMT solver for string constraints

  2016cites this paper
• A Decision Procedure for String Logic with Equations, Regular Membership and Length Constraints

  2016cites this paper
• The height of piecewise-testable languages and the complexity of the logic of subwords

  2015cites this paper
• Decidability in the Logic of Subsequences and Supersequences

  2015cites this paper
• String solving with word equations and transducers: towards a logic for analysing mutation XSS

  2015cites this paper
• Bit-vector Support in Z 3-str 2 Solver and Automated Exploit Synthesis by Sanu Edayath Subramanian

  2015cites this paper
• Automata-Based Model Counting for String Constraints

  2015cites this paper
• Effective Search-Space Pruning for Solvers of String Equations, Regular Expressions and Length Constraints

  2015influential citation
• Symbolic automata for representing big code

  2015cites this paper
• The Height of Piecewise-Testable Languages with Applications in Logical Complexity

  2015cites this paper
• Hierarchy of piecewise-testable languages and complexity of the two-variable logic of subsequences

  2015cites this paper
• Bit-vector Support in Z3-str2 Solver and Automated Exploit Synthesis

  2015cites this paper
• String Constraints for Verification

  2014cites this paper
• Automated reasoning over string constraints

  2014influential citation
• A DPLL(T) Theory Solver for a Theory of Strings and Regular Expressions

  2014cites this paper
• Symbolic Automata for Static Specification Mining

  2013cites this paper
• Z3-str: a z3-based string solver for web application analysis

  2013cites this paper
• Unification modulo Lists with Reverse Relation with Certain Word Equations

  year unknowncites this paper
• On equations and first-order theory of one-relator monoids

  year unknowncites this paper
• Alma Mater Studiorum Università di Bologna Archivio istituzionale

  year unknowncites this paper
• This paper is included in the Proceedings of the 19th USENIX Symposium on Networked Systems Design and Implementation.

  year unknowncites this paper
• Alma Mater Studiorum Università di Bologna Archivio istituzionale della ricerca

  year unknowncites this paper
• Unification modulo Lists with Reverse as Solving Simple Sets of Word Equations

  year unknowncites this paper