UC Irvine

Artificial intelligence systems are traditionally designed to solve problems that have already been defined. However, a more general form of intelligent problem solving should also support the ability to generate new problems, represent them in computational form, validate their meaning, and connect them to appropriate solution methods. This dissertation develops Generative Problem Solving (GPS) as a framework for moving from predefined problem solving toward the systematic generation, translation, validation, and solution of computational problems. The first part of this dissertation introduces GPS-Relational, a grammar-guided framework for problem solving over relational databases. The framework translates natural-language problem descriptions into executable SQL by decomposing complex requests into relational components, mapping them to database schemas, and validating their semantic compatibility before constructing the final query. A formal grammar and Semantic Validity Model provide an explicit representation of relational operations and constraints, enabling complex problems to be constructed from validated components rather than generated as unconstrained text. The same grammar also provides a foundation for systematically generating relational problem instances with controlled structure and complexity. The second part extends this generative capability by using the structured representation in the reverse direction to support the generation and verification of complex relational problems and their natural-language descriptions. Complex SQL structures are decomposed into explicit dependencies and translated into natural language, while round-trip translation and execution-based comparison are used to determine whether the generated descriptions preserve the intended relational semantics. Controlled query generation and database population further enable the creation of informative benchmark problems with varying structural complexity. Together, these mechanisms support not only problem generation, but also systematic validation and diagnosis of errors in generated problems and translations. The final part extends GPS beyond problems that can be represented and solved directly through conventional SQL. An object-relational representation is introduced to describe more complex computational structures, including graph entities, relationships, objectives, and constraints. This representation enables the generation of graph-based problems such as constrained shortest-path and influence-based optimization problems and provides a bridge from natural-language problem descriptions to the structured inputs required by specialized solvers. In this way, GPS is extended from relational query problems toward broader classes of computational problems whose solutions require algorithms beyond traditional database query processing. Together, these contributions establish a progression from translating and solving relational problems, to systematically generating and validating problems, and finally to extending problem generation beyond SQL to more general computational problem classes. The dissertation demonstrates how explicit grammars and structured representations can provide a foundation for AI systems that do more than answer predefined questions: they can construct, analyze, validate, and ultimately expand the space of problems that can be computationally explored.