Abstract
This paper discusses an approach to representing and reasoning about constraints over strings. We discuss how string domains can often be concisely represented using regular languages, and how constraints over strings, and domain operations on sets of strings, can be carried out using this representation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agrawal, R., Srikant, R.: Mining sequential patterns. In: Proceedings of the 11th International Conference on Data Engineering (1995)
Bessiere, C., Ch, J.: Arc-consistency for general constraint networks: Preliminary results. In: Proceedings of IJCAI 1997, Nagoya, Japan, August 1997, pp. 398–404 (1997)
Bitner, J.R., Reingold, E.M.: Backtrack programming techniques. Communications of the ACM 18(11), 651–656 (1975)
Eidhammer, I., Jonassen, I., Grindhaug, S.: A constraint based structure description language for biosequences. Constraints 6, 173–200 (2001)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman and Co., New York (1979)
Garofalakis, M., Rastogi, R., Shim, K.: SPIRIT:sequential pattern mining with regular expression constraints. In: Proceedings of the 25th VLDB Conference (1999)
Ginsberg, M., Frank, M., Halpin, M., Torrance, M.: Search lessons learned from crossword puzzles. In: Proceedings AAAI 1990, pp. 210–215 (1990)
Golden, K.: Automating the processing of earth observation data. In: 7th International Symposium on Artificial Intelligence, Robotics and Automation for Space (2003)
Golden, K., Frank, J.: Universal quantification in a constraint-based planner. In: AIPS 2002 (2002)
Golomb, S.W., Baumert, L.D.: Backtrack programming. Journal of the ACM 12(4), 516–524 (1965)
Hickey, T., van Emden, M., Wu, H.: A unified framework for interval constraints and interval arithmetic. In: Maher, M.J., Puget, J.-F. (eds.) CP 1998. LNCS, vol. 1520, pp. 250–264. Springer, Heidelberg (1998)
Hopcraft, J., Ullman, J.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Philippines (1979)
Jensen, T.R., Toft, B.: Graph Coloring Problems. Wiley Interscience, New York (1995)
Jónsson, A., Frank, J.: A framework for dynamic constraint reasoning using procedural constraints. In: Proceedings of ECAI 2000 (2000)
Mackworth, A.: Consistency in networks of relations. Artificial Intelligence 8(1), 99–118 (1977)
Muscettola, N.: Computing the envolope for stepwise constant resource allocations. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol. 2470, p. 139. Springer, Heidelberg (2002)
Nadel, B.A.: Consistent satisfaction algorithms. Computational Intelligence 5, 188–224 (1989)
Prosser, P.: Hybrid algorithms for the constrain satisfaction problem. Computational Intelligence 9(3), 268–299 (1993)
Rajasekar, A.: Applications in constraint logical programming with strings. In: Borning, A. (ed.) PPCP 1994. LNCS, vol. 874. Springer, Heidelberg (1994)
Rossi, F., Sperduti, A., Venable, K., Khatib, L., Morris, P., Morris, R.: Learning and solving soft temporal constraints: An experimental study. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol. 2470, p. 249. Springer, Heidelberg (2002)
Shazeer, N., Littman, M., Keim, G.: Solving crossword puzzles as probabilistic constraint satisfaction. In: Proceedings of AAAI 1999 (1999)
Waltz, D.L.: Understanding line drawings of scenes with shadows. In: Winston, P.H. (ed.) The Psychology of Computer Vision, pp. 19–91. McGraw-Hill, New York (1975)
Zweben, M., Fox, M.S.: Intelligent Scheduling. Morgan Kaufmann Publishers, San Francisco (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Golden, K., Pang, W. (2003). Constraint Reasoning over Strings. In: Rossi, F. (eds) Principles and Practice of Constraint Programming – CP 2003. CP 2003. Lecture Notes in Computer Science, vol 2833. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45193-8_26
Download citation
DOI: https://doi.org/10.1007/978-3-540-45193-8_26
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20202-8
Online ISBN: 978-3-540-45193-8
eBook Packages: Springer Book Archive