Does the HATEOAS (hypermedia as the engine of app state) recommendation imply that query strings are not RESTful?
Edit: It was suggested below that query strings may not have much to do with state and that therefore the question is puzzling. I would suggest that it doesn't make sense for the URI to have a query string unless the client were filling in arguments. If the client is filling arguments then it is adulterating the server-supplied URI and I wonder if this violates the RESTful principle.
Edit 2: I realize that the query string seems harmless if the client treats it as opaque (and the query string might be a legacy and therefore convenient). However, in one of the answers below Roy Fielding is quoted as saying that the URI should be taken to be transparent. If it is transparent then I believe adulterating is encouraged and that seems to dilute the HATEOAS principle. Is such dilution still consistent with HATEOAS? This raises the question of whether REST is calling for the tight coupling that URI building seems to be.
Update At this REST tutorial http://rest.elkstein.org/ it is suggested that URI building is bad design and is not RESTful. It also iterates what was said by @zoul in the accepted answer.
For example, a "product list" request could return an ID per product, and the specification says that you should use http://www.acme.com/product/PRODUCT_ID to get additional details. That's bad design. Rather, the response should include the actual URL with each item: http://www.acme.com/product/001263, etc. Yes, this means that the output is larger. But it also means that you can easily direct clients to new URLs as needed
If a human is looking at this list and does not want what he/she can see, there might be a "previous 10 items" and a "next 10 items" button, however, if there is no human, but rather a client program, this aspect of REST seems a little weird because of all the "http://www" that the client program may have no use for.